#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 st = 1, dr = M;
    //cout << st << ' ' << dr << endl;
    while (dr - st > 5)
    {
        int mij = (st + dr) / 2;
        for (int i = 1; i <= N; i++)
            v[i][mij] = value(i, mij), v[i][mij + 1] = value(i, mij + 1);
        int mn1 = inf, mn2 = inf;
        for (int j = 1; j <= N; j++)
        {
            mn1 = min(mn1, v[j][mij]);
            mn2 = min(mn2, v[j][mij + 1]);
        }
        if (mn1 <= mn2)
            dr = mij;
        else
            st = mij + 1;
    }
    //cout << st << ' ' << dr << endl;
    for (int i = st - 1; i <= dr + 1; i++)
    {
        if (i >= 1 and i <= M)
            for (int j = 1; j <= N; j++)
                v[j][i] = value(j, i);
    }
    for (int i = st; i <= dr; i++)
    {
        for (int j = 1; j <= N; 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);
}
