#include "locmin.h"
#include <map>
using namespace std;

map<pair<int,int>, long long> mp;

const long long INF = (long long)4e18;

long long val(int r,int c){
    if(mp.count({r,c})) return mp[{r,c}];
    return mp[{r,c}] = value(r,c);
}

bool bon(int r,int c,int N,int M){
    long long x = val(r,c);
    if(r>1 && val(r-1,c)<x) return false;
    if(r<N && val(r+1,c)<x) return false;
    if(c>1 && val(r,c-1)<x) return false;
    if(c<M && val(r,c+1)<x) return false;
    return true;
}

pair<int,int> find_locmin_point(int N,int M){
    int r = N/2, c = M/2;

    while(true){
        long long x = val(r,c);
        int nr=r, nc=c;

        if(r>1 && val(r-1,c)<x){ x=val(r-1,c); nr=r-1; nc=c; }
        if(r<N && val(r+1,c)<x){ x=val(r+1,c); nr=r+1; nc=c; }
        if(c>1 && val(r,c-1)<x){ x=val(r,c-1); nr=r; nc=c-1; }
        if(c<M && val(r,c+1)<x){ x=val(r,c+1); nr=r; nc=c+1; }

        if(nr==r && nc==c) return {r,c};
        r=nr; c=nc;
    }
}