#include "locmin.h"
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define ff first
#define sc second
#define pb push_back
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define ull unsigned long long
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rngl(chrono::steady_clock::now().time_since_epoch().count());

// #define int long long
// #define int unsigned long long

// #define ordered_set(T) tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>
// #define ordered_multiset(T) tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>

const ll mod = 1e9 + 7;
// const ll mod = 998244353;

const ll inf = 1e9;
const ll biginf = 1e18;
const int maxN = 1e6 + 15;

// static const int MAXN=500,MAXM=500;
// static long long int tab[MAXN][MAXM];
// static int n,m;
// static void finish (string message) {
//     cout << message << endl ;
//     exit(0);
// }

// static int cnt=0;
// long long int value (int row, int col) {
//     row--; col--;
//     if ((row<0)||(row>=n)||(col<0)||(col>=m)) finish("Invalid row or column number in question ("+to_string(row)+","+to_string(col)+")!");
//     cnt++;
//     if (cnt>n*m) finish("Too many questions!");
//     return tab[row][col];
// }
// extern pair <int, int> find_locmin_point (int, int);

// static int drow[]={ -1, -0, +0, +1 };
// static int dcol[]={ -0, -1, +1, +0 };
// static bool check_saddle (int row, int col) {
//     for (int i=0; i<4; i++) {
//         int r=row+drow[i],c=col+dcol[i];
//         if ((r<0)||(r>=n)||(c<0)||(c>=m)) continue;
//         if (tab[r][c]<=tab[row][col]) return false;
//     }
//     return true;
// }

ll arr[505][505], _n, _m;
ll val(int x, int y) {
    if (x < 1 || x > _n || y < 1 || y > _m) return biginf + 5;
    if (arr[x][y] == 0) arr[x][y] = value(x, y);
    return arr[x][y];
}
std::pair <int, int> find_locmin_point(int n, int m) {
    _n = n; _m = m;
    if (n == 1) {
        int l = 1, r = m, mid;
        while (l < r) {
            mid = (l + r) / 2;
            if (val(1, mid) > val(1, mid + 1)) l = mid + 1;
            else r = mid;
        }

        return {1, l};
    }

    int l1 = 1, r1 = n, l2 = 1, r2 = m;
    while (1) {
        int m1 = (l1 + r1) / 2, m2 = (l2 + r2) / 2;

        ll mn = biginf + 5, x = -1, y = -1;
        for (int i = l2; i <= r2; i++) {
            if (val(m1, i) < mn) {
                mn = val(m1, i); x = m1; y = i;
            }
        }

        for (int i = l1; i <= r1; i++) {
            if (val(i, m2) < mn) {
                mn = val(i, m2); x = i; y = m2;
            }
        }

        int x1 = x, y1 = y;
        if (val(x + 1, y) < mn) {
            mn = val(x + 1, y); x1 = x + 1; y1 = y;
        }

        if (val(x - 1, y) < mn) {
            mn = val(x - 1, y); x1 = x - 1; y1 = y;
        }

        if (val(x, y + 1) < mn) {
            mn = val(x, y + 1); x1 = x; y1 = y + 1;
        }

        if (val(x, y - 1) < mn) {
            mn = val(x, y - 1); x1 = x; y1 = y - 1;
        }

        if (x1 == x && y1 == y) return {x, y};
        if (x1 < m1) r1 = m1 - 1; else l1 = m1 + 1;
        if (y1 < m2) r2 = m2 - 1; else l2 = m2 + 1; 
    }
}


// int main () {
//     ios_base::sync_with_stdio(false);
//     cin.tie(NULL);
//     cin >> n >> m ;
//     for (int i=0; i<n; i++) {
//         for (int j=0; j<m; j++) {
//             cin >> tab[i][j] ;
//         }
//     }
//     auto [r, c]=find_locmin_point(n,m);
//     cout << "Answer cell: (" << r << "," << c << ")\n";
//     cout << "Number of value calls: " << cnt << endl ;
//     r--; c--;
//     if ((r<0)||(r>=n)||(c<0)||(c>=m)) finish("Invalid row or column in answer!");
//     if (check_saddle(r,c)==false) finish("Answer is not a local minimum point!");
//     finish("Correctly found local minimum point.");
//     return 0;
// }
