#include "locmin.h"
#include <utility>
#include <climits>

std::pair<int, int> find_locmin_point(int N, int M) {
    if (N == 1) {
        int l = 1, r = M;

        while (l < r) {
            int mid = (l + r) / 2;

            long long a = value(1, mid);
            long long b = value(1, mid + 1);

            if (a > b) l = mid + 1;
            else r = mid;
        }

        return {1, l};
    }

    int r = 1, c = 1;
    long long cur = value(r, c);

    while (true) {
        long long best = cur;
        int br = r, bc = c;

        if (r > 1) {
            long long v = value(r - 1, c);
            if (v < best) best = v, br = r - 1, bc = c;
        }
        if (r < N) {
            long long v = value(r + 1, c);
            if (v < best) best = v, br = r + 1, bc = c;
        }
        if (c > 1) {
            long long v = value(r, c - 1);
            if (v < best) best = v, br = r, bc = c - 1;
        }
        if (c < M) {
            long long v = value(r, c + 1);
            if (v < best) best = v, br = r, bc = c + 1;
        }

        if (best == cur) return {r, c};

        r = br;
        c = bc;
        cur = best;
    }
}