#include "locmin.h"
#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

const int N = 505;

ll ma[N][N];

mt19937_64 rn(chrono::steady_clock::now().time_since_epoch().count());

ll rnd(ll l, ll r) {
    return rn() % (r - l + 1) + l;
}

ll z(ll i, ll j) {
    if (ma[i][j] == -1) {
        ma[i][j] = value(i + 1, j + 1);
    }
    return ma[i][j];
}

ll n, m;

vector<int> x{-1, 1, 0, 0};
vector<int> y{0, 0, 1, -1};

bool check(ll i, ll j) {
    bool fl = 1;
    for (int k = 0; k < 4; k++) {
        int i1 = i + x[k], j1 = j + y[k];
        if (min(i1, j1) < 0 || i1 == n || j1 == m) continue;
        if (z(i1, j1) < z(i, j)) {
            fl = 0;
            break;
        }
    }
    return fl;
}

std::pair<int, int> find_locmin_point(int _n, int _m) {
    n = _n, m = _m;
    memset(ma, -1, sizeof ma);
    ll u = 0, d = n - 1, l = 0, r = m - 1;
    while (u + 2 < d || l + 2 < r) {
        ll ci = (u + d) / 2, cj = (l + r) / 2;
        ll a[n][m];
        ll mn = ll(1e18) + 1;
        for (ll i = 0; i < n; i++) {
            for (ll j = 0; j < m; j++) {
                a[i][j] = ll(1e18) + 1;
                if (i == ci || j == cj) {
                    a[i][j] = z(i, j);
                    mn = min(mn, a[i][j]);
                }
            }
        }
        ll fi, fj;
        for (ll i = 0; i < n; i++) {
            for (ll j = 0; j < m; j++) {
                if (a[i][j] == mn) {
                    if (check(i, j)) {
                        return {i + 1, j + 1};
                    } else {
                        for (ll k = 0; k < 4; k++) {
                            int i1 = i + x[k], j1 = j + y[k];
                            if (min(i1, j1) < 0 || i1 == n || j1 == m) continue;
                            if (z(i1, j1) < z(i, j)) {
                                fi = i1, fj = j1;
                                break;
                            }
                        }
                        goto link;
                    }
                }
            }
        }
        link:
        if (fi >= ci) {
            u = ci;
        } else {
            d = ci;
        }
        if (fj >= cj) {
            l = cj;
        } else {
            r = cj;
        }
    }
    ll c = 0;
    l = max(0ll, l - c), r = min((ll) m - 1, r + c);
    u = max(0ll, u - c), d = min((ll) n - 1, d + c);
    for (ll i = l; i <= r; i++) {
        for (ll j = u; j <= d; j++) {
            swap(i, j);
            if (check(i, j)) {
                return {i + 1, j + 1};
            }
            swap(i, j);
        }
    }
    assert(0);
}
