#include "locmin.h"
#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

const int N = 505;

ll ma[N][N];

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

ll rnd(ll l, ll r) {
    return rn() % (r - l + 1) + l;
}

ll z(ll i, ll j) {
    if (ma[i][j] == -1) {
        ma[i][j] = value(i + 1, j + 1);
    }
    return ma[i][j];
}

std::pair<int, int> find_locmin_point(int n, int m) {
    memset(ma, -1, sizeof ma);
    ll l = 0, r = m - 1;
    while (l + 2 < r) {
        ll xl = z(0, l), xr = z(0, r);
        ll il = l + (r - l) / 3, ir = r - (r - l) / 3;
        ll fl = z(0, il), fr = z(0, ir);
        ll mn = min({xl, xr, fl, fr});
        if (xl == mn) {
            r = il;
        } else if (xr == mn) {
            l = ir;
        } else if (fl == mn) {
            r = ir;
        } else {
            l = il;
        }
    }
    if (l == r) {
        return {1, l + 1};
    } else if (l + 1 == r) {
        if (z(0, l) < z(0, r)) {
            return {1, l + 1};
        } else {
            return {1, r + 1};
        }
    } else {
        ll xl = z(0, l), xr = z(0, r);
        ll f = z(0, l + 1);
        ll mn = min({xl, xr, f});
        if (xl == mn) {
            return {1, l + 1};
        } else if (f == mn) {
            return {1, l + 2};
        } else {
            return {1, l + 3};
        }
    }
}
