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

bool know[505][505];
int N, M, cnt;
ll mat[505][505];

ll getvalue(int i, int j){
    if(i == 0 || j == 0) return 1e18 + 1;
    if(i > N || j > M) return 1e18 + 1;
    if(cnt == N * M) assert(0);
    cnt++;
    return value(i, j);
}

bool check(int i, int j){
    bool ok = 1;
    if(!know[i - 1][j]){
        know[i - 1][j] = 1;
        mat[i - 1][j] = getvalue(i - 1, j);
    }
    if(mat[i - 1][j] < mat[i][j]) return 0;
    if(!know[i + 1][j]){
        know[i + 1][j] = 1;
        mat[i + 1][j] = getvalue(i + 1, j);
    }
    if(mat[i + 1][j] < mat[i][j]) return 0;
    if(!know[i][j - 1]){
        know[i][j - 1] = 1;
        mat[i][j - 1] = getvalue(i, j - 1);
    }
    if(mat[i][j - 1] < mat[i][j]) return 0;
    if(!know[i][j + 1]){
        know[i][j + 1] = 1;
        mat[i][j + 1] = getvalue(i, j + 1);
    }
    if(mat[i][j + 1] < mat[i][j]) return 0;
    return 1;
}

pair<int, int> getmin(int li, int ri, int lj, int rj){
    if(li == ri && lj == rj){
        return {li, lj};
    }
    if(ri - li <= rj - lj){
        int split = lj + rj >> 1;
        int imin = -1;
        for(int i = li; i <= ri; i++){
            if(!know[i][split]){
                know[i][split] = 1;
                mat[i][split] = getvalue(i, split);
            }
            if(imin == -1 || mat[i][split] < mat[i][imin])
                imin = i;
        }
        if(check(imin, split))
            return {imin, split};
        if(mat[imin][split - 1] < mat[imin][split] && split - 1 >= lj){
            return getmin(li, ri, lj, split - 1);
        }
        return getmin(li, ri, split + 1, rj);
    }
    int split = li + ri >> 1;
    int jmin = -1;
    for(int j = lj; j <= rj; j++){
        if(!know[split][j]){
            know[split][j] = 1;
            mat[split][j] = getvalue(split, j);
        }
        if(jmin == -1 || mat[split][j] < mat[split][jmin])
            jmin = j;
    }
    if(check(jmin, split))
        return {jmin, split};
    if(mat[split - 1][jmin] < mat[split][jmin] && split - 1 >= li)
        return getmin(li, split - 1, lj, rj);
    return getmin(split + 1, ri, lj, rj);
}

pair<int, int> find_locmin_point(int n, int m){
    assert(0);
    N = n;
    M = m;
    for(int i = 0; i <= n + 1; i++){
        know[i][0] = know[i][m + 1] = 1;
        mat[i][0] = mat[i][m + 1] = 1e18 + 1;
    }
    for(int j = 0; j <= m + 1; j++){
        know[0][j] = know[n + 1][j] = 1;
        mat[0][j] = mat[n + 1][j] = 1e18 + 1;
    }
    return getmin(1, n, 1, m);
}

