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

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

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

pair<int,int> recL(int n,int m,int h,int b,int g,int d){
    int mid=(h+b)/2;

    int bc=1;
    long long bv=val(mid,1);

    for(int j=2;j<=m;j++){
        long long v=val(mid,j);
        if(v<bv){bv=v;bc=j;}
    }

    long long vg,vd;
    if(mid>1) vg=val(mid-1,bc);
    else vg=1e18;
    if(mid<n) vd=val(mid+1,bc);
    else vd=1e18;

    if(bv<vg && bv<vd) return {mid,bc};
    if(vg<bv) return recL(n,m,h,mid-1,g,d);
    return recL(n,m,mid+1,b,d,g,d);
}

pair<int,int> recC(int n,int m,int g,int d){
    int mid=(g+d)/2;

    int br=1;
    long long bv=val(1,mid);

    for(int i=2;i<=n;i++){
        long long v=val(i,mid);
        if(v<bv){bv=v;br=i;}
    }

    long long vg,vd;
    if(mid>1) vg=val(br,mid-1);
    else vg=1e18;
    if(mid<m) vd=val(br,mid+1);
    else vd=1e18;

    if(bv<vg && bv<vd) return {br,mid};
    if(vg<bv) return recC(n,m,g,mid-1);
    return recC(n,m,mid+1,d);
}

pair<int,int> find_locmin_point(int N,int M){
    if(N < M) return recL(N,M,1,N,1,M);
    return recC(N,M,1,M);
}