#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];
    };

    const auto binr = [N, M, &v] (int r1, int c1, int delta) {
        int l = delta < 0 ? 0 : r1 + 1, r = delta < 0 ? r1 : N;
        while (l < r) {
            int m = (l + r) / 2;
            if (v(m - 1, c1) < v(m, c1)) r = m;
            else if (v(m, c1) > v(m + 1, c1)) l = m + 1;
            else return m;
        }
        return l;
    };

    const auto binc = [N, M, &v] (int r1, int c1, int delta) {
        int l = delta < 0 ? 0 : c1 + 1, r = delta < 0 ? c1 : M;
        while (l < r) {
            int m = (l + r) / 2;
            if (v(r1, m - 1) < v(r1, m)) r = m;
            else if (v(r1, m) > v(r1, m + 1)) l = m + 1;
            else return m;
        }
        return l;
    };

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