#include "locmin.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

static const ll INF = (ll)4e18;
static const int MAXN = 505;

static ll ma[MAXN][MAXN];
static int n_, m_;

static ll z(int i, int j) { // i,j are 0-based, guaranteed in-bounds
    if (ma[i][j] == -1) ma[i][j] = value(i + 1, j + 1);
    return ma[i][j];
}

static inline ll getv(int i, int j) { // safe for out-of-bounds
    if (i < 0 || i >= n_ || j < 0 || j >= m_) return INF;
    return z(i, j);
}

static bool is_locmin(int i, int j) {
    ll v = getv(i, j);
    return v < getv(i-1, j) && v < getv(i+1, j) && v < getv(i, j-1) && v < getv(i, j+1);
}

static pair<int,int> solve(int r1, int r2, int c1, int c2) { // inclusive, 0-based
    // small base: brute force inside rectangle (but check neighbors in whole grid via getv)
    if (r2 - r1 + 1 <= 3 && c2 - c1 + 1 <= 3) {
        for (int i = r1; i <= r2; i++)
            for (int j = c1; j <= c2; j++)
                if (is_locmin(i, j)) return {i, j};

        // theoretically shouldn't happen, but as fallback return min in rect
        int bi = r1, bj = c1;
        for (int i = r1; i <= r2; i++)
            for (int j = c1; j <= c2; j++)
                if (getv(i,j) < getv(bi,bj)) bi=i, bj=j;
        return {bi, bj};
    }

    int rm = (r1 + r2) / 2;
    int cm = (c1 + c2) / 2;

    // find minimum on the cross: middle row + middle column
    int bi = rm, bj = c1;
    ll best = getv(bi, bj);

    for (int j = c1; j <= c2; j++) {
        ll v = getv(rm, j);
        if (v < best) best = v, bi = rm, bj = j;
    }
    for (int i = r1; i <= r2; i++) {
        ll v = getv(i, cm);
        if (v < best) best = v, bi = i, bj = cm;
    }

    if (is_locmin(bi, bj)) return {bi, bj};

    // pick strictly smaller neighbor (it exists if not local min)
    int ni = bi, nj = bj;
    ll cur = getv(bi, bj);

    const int di[4] = {-1, +1, 0, 0};
    const int dj[4] = {0, 0, -1, +1};
    for (int k = 0; k < 4; k++) {
        int ti = bi + di[k], tj = bj + dj[k];
        ll v = getv(ti, tj);
        if (v < cur) cur = v, ni = ti, nj = tj;
    }

    // go to the quadrant that contains (ni,nj), excluding the cross lines
    int nr1, nr2, nc1, nc2;

    if (ni < rm) { nr1 = r1; nr2 = rm - 1; }
    else         { nr1 = rm + 1; nr2 = r2; }

    if (nj < cm) { nc1 = c1; nc2 = cm - 1; }
    else         { nc1 = cm + 1; nc2 = c2; }

    // Safety: if some side became empty due to small sizes, brute force whole rect
    if (nr1 > nr2 || nc1 > nc2) {
        // fallback brute in current rectangle
        for (int i = r1; i <= r2; i++)
            for (int j = c1; j <= c2; j++)
                if (is_locmin(i, j)) return {i, j};
        // last resort
        return {bi, bj};
    }

    return solve(nr1, nr2, nc1, nc2);
}

pair<int,int> find_locmin_point(int n, int m) {
    n_ = n; m_ = m;
    memset(ma, -1, sizeof(ma));

    auto [ri, rj] = solve(0, n-1, 0, m-1);
    return {ri + 1, rj + 1}; // to 1-based
}