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

long long inf = 1e18;
using namespace std;

map<pair<int,int>,long long> mapa;
int n,m;

long long findV(pair<int,int> x)
{
    if(x.first < 1 || x.second < 1 || x.first > n || x.second > m) return inf;
    if(mapa.count(x)) return mapa[x];
    return mapa[x] = value(x.first, x.second);
}

pair<int,int> solve(int a1, int a2, int b1, int b2)
{
    if(a1 == a2 && b1 == b2) return {a1, b1};

    int mida = a1 + a2 >> 1;
    int midb = b1 + b2 >> 1;

    long long mn = inf;
    int tl = -1, tr = -1;

    for(int i = b1; i <= b2; i++)
    {
        long long v = findV({mida, i});
        if(v < mn)
        {
            mn = v;
            tl = mida;
            tr = i;
        }
    }

    for(int i = a1; i <= a2; i++)
    {
        long long v = findV({i, midb});
        if(v < mn)
        {
            mn = v;
            tl = i;
            tr = midb;
        }
    }

    long long v = findV({tl, tr});
    long long gore = findV({tl-1, tr});
    long long dole = findV({tl+1, tr});
    long long levo = findV({tl, tr-1});
    long long desno = findV({tl, tr+1});

    if(v < levo && v < desno && v < gore && v < dole)
        return {tl, tr};

    if(gore < v)
    {
        if(tr <= midb) return solve(a1, mida-1, b1, midb);
        else return solve(a1, mida-1, midb+1, b2);
    }
    if(dole < v)
    {
        if(tr <= midb) return solve(mida+1, a2, b1, midb);
        else return solve(mida+1, a2, midb+1, b2);
    }
    if(levo < v)
    {
        if(tl <= mida) return solve(a1, mida, b1, midb-1);
        else return solve(mida+1, a2, b1, midb-1);
    }
    if(desno < v)
    {
        if(tl <= mida) return solve(a1, mida, midb+1, b2);
        else return solve(mida+1, a2, midb+1, b2);
    }

    return {tl, tr};
}

std::pair <int, int> find_locmin_point(int N, int M)
{
    n = N;
    m = M;
    if(N == 1)
    {
        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 return solve(1, n, 1, m);
}
