#include "locmin.h"
#include<bits/stdc++.h>
using namespace std;
long long a[507][507];
bool u[507][507];
long long val(int r,int c)
{
    if(u[r][c])
    {
        return a[r][c];
    }
    u[r][c]=1;
    a[r][c]=value(r,c);
    return a[r][c];
}
std::pair <int, int> find_locmin_point(int N, int M) {
    int lc=1,rc=M;
    int lr=1,rr=N;
    for(int i=1;i<=500;i++)
    {
        for(int j=1;j<=500;j++)
        {
            u[i][j]=0;
        }
    }
    for(int i=1;i<=500;i++)
    {
        u[0][i]=1;
        u[i][0]=1;
        u[N+1][i]=1;
        u[i][M+1]=1;
    }
    while(lc<rc || lr<rr)
    {
        if(rr-lr+1<rc-lc+1)
        {
            int mc=(lc+rc)/2;
            assert(mc+1<=rc);
            long long m1=LLONG_MAX;
            long long mi=LLONG_MAX;
            for(int i=lr;i<=rr;i++)
            {
                if(val(i,mc)<m1)
                {
                    m1=val(i,mc);
                    mi=i;
                }
            }
            if(m1<val(mi,mc+1))
            {
                rc=mc;
            }
            else
            {
                lc=mc+1;
            }
        }
        else if(lr<rr)
        {
            int mr=(lr+rr)/2;
            assert(mr+1<=rr);
            long long m1=LLONG_MAX;
            long long mi;
            for(int i=lc;i<=rc;i++)
            {
                if(val(mr,i)<m1)
                {
                    m1=val(mr,i);
                    mi=i;
                }
            }
            if(m1<val(mr+1,mi))
            {
                rr=mr;
            }
            else
            {
                lr=mr+1;
            }
        }
    }
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=M;j++)
        {
            if(u[i][j])
            {
                if(!u[i+1][j] || !u[i-1][j] || !u[i][j-1] || !u[i][j+1])
                {
                    continue;
                }
                if(i!=N && a[i+1][j]<a[i][j])
                {
                    continue;
                }
                if(j!=M && a[i][j+1]<a[i][j])
                {
                    continue;
                }
                if(i!=1 && a[i-1][j]<a[i][j])
                {
                    continue;
                }
                if(j!=1 && a[i][j-1]<a[i][j])
                {
                    continue;
                }
                return {i,j};
            }
        }
    }
    return {lr,lc};
}
