#include <bits/stdc++.h>
#include "locmin.h"


long long inf = 1e18;
using namespace std;
std::pair <int, int> find_locmin_point(int N, int M) {
    if(N == 1)
    {
        std::map<std::pair<int,int>,long long> mapa;
        if(M == 1)return {1,1};
        int tl = 1;
        int tr = M;
        long long rez = inf;
        while(tl <= tr)
        {
            int mid = tl+tr>>1;
            long long left = inf;
            long long right = inf;
            long long v;
            if(mapa.count({1,mid}))v = mapa[{1,mid}];
            else v = value(1,mid), mapa[{1,mid}] = v;

            if(mid>1)
            {
                if(mapa.count({1,mid-1}))left = mapa[{1,mid-1}];
                else left = value(1,mid-1), mapa[{1,mid-1}] = left;
            }
            if(mid<M)
            {
                if(mapa.count({1,mid+1}))right = mapa[{1,mid+1}];
                else right = value(1,mid+1), mapa[{1,mid+1}] = right;
            }
            if(v < left && v < right)
            {
                rez = mid;
                break;
            }
            else if(v >= left)tr = mid-1;
            else tl = mid+1;
        }
        if(rez == inf)rez = tl+tr>>1;
        return {1,rez};
    }
    else
    {
        set<pair<int,int>> setic;
        map<pair<int,int>,long long> mapa;
        for(int j=1; j<=N; j++)
        {
            if(M == 1)setic.insert({1,1});
            else
            {

                int tl = 1;
                int tr = M;
                long long rez = inf;
                while(tl <= tr)
                {
                    int mid = tl+tr>>1;
                    long long left = inf;
                    long long right = inf;
                    long long v;
                    if(mapa.count({j,mid}))v = mapa[{j,mid}];
                    else v = value(j,mid), mapa[{j,mid}] = v;

                    if(mid>1)
                    {
                        if(mapa.count({j,mid-1}))left = mapa[{j,mid-1}];
                        else left = value(j,mid-1), mapa[{j,mid-1}] = left;
                    }
                    if(mid<M)
                    {
                        if(mapa.count({j,mid+1}))right = mapa[{j,mid+1}];
                        else right = value(j,mid+1), mapa[{j,mid+1}] = right;
                    }
                    if(v < left && v < right)
                    {
                        rez = mid;
                        break;
                    }
                    else if(v >= left)tr = mid-1;
                    else tl = mid+1;
                }
                if(rez == inf)rez = tl+tr>>1;
                setic.insert({j,rez});
            }
        }
        for(auto x: setic)
        {
            pair<int,int> tr = x;
            long long v = mapa[tr];
            long long gore = inf;
            long long dole = inf;
            long long levo = inf;
            long long desno = inf;
            if(tr.first > 1)
            {
                if(mapa.count({tr.first-1,tr.second}))gore = mapa[{tr.first-1,tr.second}];
                else gore = value(tr.first-1,tr.second), mapa[{tr.first-1,tr.second}] = gore;
            }
            if(tr.first < N)
            {
                if(mapa.count({tr.first+1,tr.second}))dole = mapa[{tr.first+1,tr.second}];
                else dole = value(tr.first+1,tr.second), mapa[{tr.first+1,tr.second}] = dole;
            }
            if(tr.second > 1)
            {
                if(mapa.count({tr.first,tr.second-1}))levo = mapa[{tr.first,tr.second-1}];
                else levo = value(tr.first,tr.second-1), mapa[{tr.first,tr.second-1}] = levo;
            }
            if(tr.second < M)
            {
                if(mapa.count({tr.first,tr.second+1}))desno = mapa[{tr.first,tr.second+1}];
                else desno = value(tr.first,tr.second+1), mapa[{tr.first,tr.second+1}] = desno;
            }
            if(v < levo && v<desno && v < gore && v < dole)return tr;

        }

        return {1,1};
    }
}
