#include "locmin.h"
#include <bits/stdc++.h>
using namespace std;
const long long inf = 2e18;
pair <int, int> find_locmin_point(int n, int m){
    vector<int> dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0};
    vector<vector<long long>> p(n + 1, vector<long long>(m + 1));
    auto get = [&](int x, int y){
        if(x < 1 || x > n || y < 1 || y > m) return inf;
        if(!p[x][y]) p[x][y] = value(x, y);
        return p[x][y];
    };
    auto find = [&](int i, int l){
        int r = m;
        while(l < r){
            int mid = (l + r) / 2;
            long long a = get(i, mid - 1), cur = get(i, mid), b = get(i, mid + 1);
            if(cur < a && cur < b){
                return mid;
            }else if(cur > a){
                r = mid;
            }else{
                l = mid + 1;
            }
        }
        if(get(i, l) < min(get(i, l - 1), get(i, l + 1))) return l;
        return -1;
    };
    vector<int> ord;
    for(int i = 1; i <= n; i++) ord.push_back(i);
    random_shuffle(ord.begin(), ord.end());
    vector<int> pos(n + 1, 1);
    while(1){
        random_shuffle(ord.begin(), ord.end());
        for(auto i : ord){
            if(pos[i] <= m){
                int k = find(i, pos[i]);
                if(k == -1){
                    pos[i] = m + 1;
                    continue;
                }
                if(get(i, k) < min(get(i - 1, k), get(i + 1, k))) return {i, k};
                pos[i] = k + 1;
            }
        }
    }
}
