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

std::pair<int, int> find_locmin_point(int N, int M) {
    int left = 1, right = M;

    while (left <= right) {
        int mid = (left + right) / 2;

        int bestRow = 1;
        long long bestVal = value(1, mid);

        for (int i = 2; i <= N; i++) {
            long long v = value(i, mid);
            if (v < bestVal) {
                bestVal = v;
                bestRow = i;
            }
        }

        int r = bestRow;
        int c = mid;

        long long cur = bestVal;

        long long leftVal = (c > 1) ? value(r, c - 1) : LLONG_MAX;
        long long rightVal = (c < M) ? value(r, c + 1) : LLONG_MAX;

        if (cur < leftVal && cur < rightVal) {
            return {r, c};
        }

        if (c > 1 && leftVal < cur) {
            right = mid - 1;
        } else if (c < M && rightVal < cur) {
            left = mid + 1;
        } else {
            return {r, c};
        }
    }

    return {1, 1};
}