#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));
    int l = 1, r = m;
    while(l < r){
        int mid = (l + r) / 2;
        if(!p[n][mid]) p[n][mid] = value(n, mid);
        long long a = inf, b = inf;
        if(mid > 1){
            if(!p[n][mid - 1]) p[n][mid - 1] = value(n, mid - 1);
            a = p[n][mid - 1];
        }
        if(mid < m){
            if(!p[n][mid + 1]) p[n][mid + 1] = value(n, mid + 1);
            b = p[n][mid + 1];
        }
        long long cur = p[n][mid];
        if(cur < a && cur < b){
            return {n, mid};
        }else if(cur > a){
            r = mid;
        }else{
            l = mid + 1;
        }
    }
    return {n, l};
}
