#include "locmin.h"
#include<bits/stdc++.h>
using namespace std;

const long long MAXN = 507, INF = 1000000000000000007;
long long n, m, ans[MAXN][MAXN];
bool vis[MAXN][MAXN];

long long query(long long x, long long y)
{
    if(x < 1 || x > n || y < 1 || y > m) return INF;
    long long c1;
    if(vis[x][y]) c1 = ans[x][y];
    else c1 = value(x, y);
    vis[x][y] = true;
    ans[x][y] = c1;
    return c1;
}

pair<int, int> find_locmin_point(int N, int M)
{
    n = N;
    m = M;
    long long l1 = 1, r1 = n, l2 = 1, r2 = m, mid;
    while(r1 > l1 || r2 > l2)
    {
        long long mini = INF;
        pair<long long, long long> minii;
        if(r1 > l1)
        {
            mid = (l1+r1)/2;
            for(long long i = l2; i <= r2; i++)
            {
                long long c1 = query(mid, i);
                if(c1 < mini)
                {
                    mini = c1;
                    minii = {mid, i};
                }
            }
        }
        if(r2 > l2)
        {
            mid = (l2+r2)/2;
            for(long long i = l1; i <= r1; i++)
            {
                long long c1 = query(i, mid);
                if(c1 < mini)
                {
                    mini = c1;
                    minii = {i, mid};
                }
            }
        }
        int mid1 = (l1+r1)/2, mid2 = (l2+r2)/2, x = minii.first, y = minii.second;
        if(x == mid1 && y == mid2) return {x, y};
        if(x == mid1)
        {
            long long c1 = query(x-1, y), c2 = query(x+1, y);
            if(ans[x][y] < c1 && ans[x][y] < c2) return {x, y};
            if(c1 < ans[x][y])
            {
                r1 = x-1;
                if(y < mid2) r2 = mid2;
                else l2 = mid2;
            }
            else
            {
                l1 = x+1;
                if(y < mid2) r2 = mid2;
                else l2 = mid2;
            }
        }
        else
        {
            long long c1 = query(x, y-1), c2 = query(x, y+1);
            if(ans[x][y] < c1 && ans[x][y] < c2) return {x, y};
            if(c1 < ans[x][y])
            {
                r2 = y-1;
                if(x < mid1) r1 = mid1;
                else l1 = mid1;
            }
            else
            {
                l2 = y+1;
                if(x < mid1) r1 = mid1;
                else l1 = mid1;
            }
        }
    }
    return {l1, l2};
}
