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

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

    while (true) {
        int mid = (l + r) / 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 x = bestRow;
        int y = mid;

        long long cur = bestVal;

        long long leftVal;
        if (y > 1) {
            leftVal = value(x, y - 1);
        } else {
            leftVal = LLONG_MAX;
        }

        long long rightVal;
        if (y < M) {
            rightVal = value(x, y + 1);
        } else {
            rightVal = LLONG_MAX;
        }

        if (cur < leftVal && cur < rightVal) {
            return {x, y};
        }

        if (y > 1 && leftVal < cur) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
}