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

using namespace std;

static int drow[]={ -1, -0, +0, +1 };
static int dcol[]={ -0, -1, +1, +0 };

mt19937 rng(time(0));

pair <int, int> f(int N, int M, int it) {
    vector<vector<long long>> w(N + 1, vector<long long>(M + 1, 0));
    auto query = [&](int x, int y) {
        if (w[x][y] == 0) {
            w[x][y] = value(x, y);
            --it;
        }
        return w[x][y];
    };

    int ptrx = rng() % N + 1, ptry = rng() % M + 1;
    long long val = query(ptrx, ptry);

    vector<array<long long, 3>> in;
    auto add = [&](int x, int y) {
        if (x < 1 || x > N || y < 1 || y > M) {
            return;
        }

        long long v = query(x, y);
        if (v >= val) {
            return;
        }

        in.push_back({v, x, y});
    };

    while (1) {
        in.clear();
        for (int i = 0; i < 4; ++i) {
            add(ptrx + drow[i], ptry + dcol[i]);
        }

        if (in.empty()) {
            return {ptrx, ptry};
        }

        sort(in.begin(), in.end());

        val = in[0][0];
        ptrx = in[0][1], ptry = in[0][2];
    }

    return {-1, -1};
}

pair <int, int> find_locmin_point(int N, int M) {
    int tot = N * M;
    while (tot) {
        int q = (N == 1 ? 2 : rng() % tot + 1);
        tot -= q;

        auto [x, y] = f(N, M, q);
        if (x != -1 && y != -1) {
            return {x, y};
        }
    }
    return {-1, -1};
}
