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

using namespace std;

using integer = int;

#define int long long

const int inf = 2e18;

pair<integer,integer> find_locmin_point(integer N, integer M)
{
    //cout << N << ' ' << M << endl;
    vector<vector<int>> v;
    v.resize(N + 2);
    for (int i = 0; i < N + 2; i++)
        v[i].resize(M + 2);
    for (int i = 0; i < N + 2; i++)
    {
        for (int j = 0; j < M + 2; j++)
        {
            if (i == 0 or i == N + 1 or j == 0 or j == M + 1)
                v[i][j] = inf;
            else
                v[i][j] = -1;
        }
    }
    int st1 = 1, dr1 = M, st2 = 1, dr2 = N;
    //cout << st << ' ' << dr << endl;
    while (dr1 - st1 > 5 or dr2 - st2 > 5)
    {
        if (dr1 - st1 > dr2 - st2)
        {
            int mij = (st1 + dr1) / 2;
            for (int i = st2; i <= dr2; i++)
                v[i][mij] = value(i, mij), v[i][mij + 1] = value(i, mij + 1);
            int mn1 = inf, mn2 = inf;
            for (int j = st2; j <= dr2; j++)
            {
                mn1 = min(mn1, v[j][mij]);
                mn2 = min(mn2, v[j][mij + 1]);
            }
            if (mn1 <= mn2)
                dr1 = mij;
            else
                st1 = mij + 1;
        }
        else
        {
            int mij = (st2 + dr2 / 2);
            for (int i = st1; i <= dr1; i++)
                v[mij][i] = value(mij, i), v[mij + 1][i] = value(mij + 1, i);
            int mn1 = inf, mn2 = inf;
            for (int i = st1; i <= dr1; i++)
            {
                mn1 = min(mn1, v[mij][i]);
                mn2 = min(mn2, v[mij + 1][i]);
            }
            if (mn1 <= mn2)
                dr2 = mij;
            else
                st2 = mij + 1;
        }
    }
    for (int i = st1 - 1; i <= dr1 + 1; i++)
    {
        if (i >= 1 and i <= M)
            for (int j = st2 - 1; j <= dr2 + 1; j++)
                if (j >= 1 and j <= N)
                    v[j][i] = value(j, i);
    }
    for (int i = st1; i <= dr1; i++)
    {
        for (int j = st2; j <= dr2; j++)
        {
            if (v[j][i] < v[j - 1][i] and v[j][i] < v[j + 1][i] and v[j][i] < v[j][i - 1] and v[j][i] < v[j][i + 1])
                return {j, i};
        }
    }
    assert(false);
}
