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

using namespace std;

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

map<pair<int, int>, long long> mp;

long long query(int x, int y) {
    if (!mp.count({x, y})) {
        mp[{x, y}] = value(x, y);
    }
    return mp[{x, y}];
}

mt19937 rng(time(0));

pair <int, int> find_locmin_point(int N, int M) {
    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) {
        for (int i = 0; i < 4; ++i) {
            add(ptrx + drow[i], ptry + dcol[i]);
        }

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

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

        int p = rng() % in.size();

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

    return {ptrx, ptry};
}
