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

using namespace std;

typedef long long ll;

vector<vector<ll>> valarr;

ll get(ll i, ll j)
{
    if(valarr[i][j] != -1) return valarr[i][j];
    return valarr[i][j] = value(i+1, j+1);
}

ll heightg, widthg;
bool test(ll lh, ll lw)
{
    bool good = true;
    good &= lh == 0 || get(lh-1, lw) > get(lh, lw);
    good &= lh == heightg-1 || get(lh+1, lw) > get(lh, lw);
    good &= lw == 0 || get(lh, lw-1) > get(lh, lw);
    good &= lw == widthg-1 || get(lh, lw+1) > get(lh, lw);
    return good;
}

std::pair <int, int> find_locmin_point(int height, int width)
{
    heightg = height;
    widthg = width;
    valarr.assign(height, vector<ll>(width, -1));
    ll lh = 0, rh = height-1, lw = 0, rw = width-1, mid, l, r;
    ll small, smalli;
    while(rh > lh || rw > lw)
    {
        if(rh - lh >= rw - lw && lh < rh)
        {
            mid = (lh + rh) / 2;
            small = LLONG_MAX;
            for(ll i = lw; i <= rw; i++)
            {
                ll val = get(mid, i);
                if(val < small)
                {
                    small = val;
                    smalli = i;
                }
            }
            l = mid > 0 ? get(mid-1, smalli) : LLONG_MAX; // up
            r = mid < height-1 ? get(mid+1, smalli) : LLONG_MAX; // down
            if(small < l && small < r && test(mid, smalli)) return {mid+1, smalli+1};
            if(l < r)
            {
                rh = mid;
            }
            else
            {
                lh = mid+1;
            }
        }
        else
        {
            mid = (lw + rw) / 2;
            small = LLONG_MAX;
            for(ll i = lh; i <= rh; i++)
            {
                ll val = get(i, mid);
                if(val < small)
                {
                    small = val;
                    smalli = i;
                }
            }
            l = mid > 0 ? get(smalli, mid-1) : LLONG_MAX; // left
            r = mid < width-1 ? get(smalli, mid+1) : LLONG_MAX; // right
            if(small < l && small < r && test(smalli, mid)) return {smalli+1, mid+1};
            if(l < r)
            {
                rw = mid;
            }
            else
            {
                lw = mid+1;
            }
        }
    }
    bool good = true;
    good &= lh == 0 || get(lh-1, lw) > get(lh, lw);
    good &= lh == height-1 || get(lh+1, lw) > get(lh, lw);
    good &= lw == 0 || get(lh, lw-1) > get(lh, lw);
    good &= lw == width-1 || get(lh, lw+1) > get(lh, lw);
    if(!good) return {1/0, 1};
    return {lh+1, lw+1};
}