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

vector<pair<int, int>> delta = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

int n, m;
vector<vector<int>> g;

bool ok(int i, int j) {
    if (g[i][j] == -1) g[i][j] = value(i, j);
    for (auto [pi, pj]: delta) {
        if (i + pi <= 0 || i + pi > n || j + pj <= 0 || j + pj > m) continue;
        if (g[i + pi][j + pj] == -1) g[i + pi][j + pj] = value(i + pi, j + pj);
        if (g[i + pi][j + pj] < g[i][j]) return false;
    }
    return true;
}

pair<int, int> find_locmin_point(int N, int M) {
    n = N;
    m = M;
    g.assign(n+1, vector<int>(m+1, -1));
    if (ok(1, m)) return {1, m};
    int lo = 1, hi = m-1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (ok(1, mid)) {
            return {1, mid};
        }
        if (g[1][mid] > g[1][mid+1]) {
            lo = mid+1;
        }
        else {
            hi = mid-1;
        }
    }
    assert(false);
    return {-1, -1};
}
