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

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

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

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

        // trouver le minimum dans la colonne 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) : (long long)4e18;
        long long rightVal = (c < M) ? value(r, c + 1) : (long long)4e18;

        // si local minimum
        if (cur < leftVal && cur < rightVal) {
            return {r, c};
        }

        // aller du côté où il y a un plus petit voisin
        if (leftVal < cur && leftVal < rightVal) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
}