#include <stdint.h>
#include <limits.h>
#include <vector>
#include "locmin.h"

std::pair<int, int> find_locmin_point(int N, int M) {
    std::vector<long long> values(N * M, 0);
    const auto v = [N, M, &values] (int r, int c) {
        if (r < 0 || c < 0 || r >= N || c >= M) return LLONG_MAX;
        if (values[r * M + c] == 0) values[r * M + c] = value(r + 1, c + 1);
        return values[r * M + c];
    };

    if (N > 1) {
        int r = N / 2, c = M / 2;
        while (true) {
            if (v(r - 1, c) < v(r, c)) r--;
            else if (v(r, c - 1) < v(r, c)) c--;
            else if (v(r + 1, c) < v(r, c)) r++;
            else if (v(r, c + 1) < v(r, c)) c++;
            else return { r + 1, c + 1 };
        }
    }

    int lr = 0, rr = N;
    int lc = 0, rc = M;
    while (lr < rr || lc < rc) {
        int mr = (lr + rr) / 2;
        int mc = (lc + rc) / 2;
        if (lr < rr) {
            if (v(mr - 1, mc) < v(mr, mc)) rr = mr;
            else if (v(mr, mc) > v(mr + 1, mc)) lr = mr + 1;
            else lr = rr = mr;
        }
        if (lc < rc) {
            if (v(mr, mc - 1) < v(mr, mc)) rc = mc;
            else if (v(mr, mc) > v(mr, mc + 1)) lc = mc + 1;
            else lr = rr = mr;
        }
    }
    return { lr + 1, lc + 1 };
}
