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

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define sort_uniq(x) sort(all(x)), uniq(x);
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define V vector
#define V2dll V<V<ll>>
#define V2dint V<V<int>>
#define V2dchar V<V<char>>
#define V2dbool V<V<bool>>
#define V3dll V<V<V<ll>>>
#define V3dint V<V<V<int>>>
#define V3dchar V<V<V<char>>>
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define INF INT32_MAX
#define blt __builtin_popcount
#define clr(x) x.clear()
#define ff first
#define ss second
#define popf pop_front
#define popb pop_back
#define sz(x) int(x.size())
#define rep(a,b,c,d) for(int a = b;a <= c; a += d)
#define repl(a,b,c,d) for(int a = b; a >= c; a -= d)

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

const int N = 505;
ll tv[N];

ll table[N][N];

void get(int pos) {
    if (tv[pos]) return;
    tv[pos] = value(1, pos);
}

ll val(pii pos) {
    if (table[pos.ff][pos.ss])  return table[pos.ff][pos.ss];
    return table[pos.ff][pos.ss] = value(pos.ff, pos.ss);
}

ll solve(int l, int r) { // [l, r) 
    if (r - l + 1 <= 6) {
        get(l);
        get(l + 1);
        if (tv[l] < tv[l + 1])
            return l;
        rep(i, l + 2, r, 1)
            get(i);
        rep(i, l + 1, r - 1, 1) {
            if (tv[i] < tv[i - 1] && tv[i] < tv[i + 1]) 
                return i;
        }
    }
    int mid = l + r >> 1;
    get(l);
    get(mid);
    if (tv[l] <= tv[mid]) 
        return solve(l, mid);
    get(mid - 1);
    if (tv[mid] < tv[mid - 1]) {
        return solve(mid, r);
    }
    return solve(l, mid);
}    

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

pair <int, int> find_locmin_point(int n, int m) {
    if (n == 1) {
        tv[m + 1] = 1e18 + 100;
        return {1, solve(1, m + 1)};
    }
    rep(i, 0, N - 1, 1) {
        table[0][i] = table[i][0] = 1e18 + 100;
    }
    pii pos = {1, 1};
    bool solved = true;
    while (true) {
        rep(i, 0, 3, 1) {
            pii cur = {pos.ff + dx[i], pos.ss + dy[i]};
            if (val(cur) < val(pos)) {
                pos = cur;
                solved = false;
                break;
            }
        }
        if (solved)
            return {pos.ff, pos.ss};
        solved = true;
    }
}
