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

using namespace std;

map<pair<int, int>, int> bf;

int get(int x, int y) {
    if (bf.find({ x, y }) != bf.end()) return bf[{x, y}];
    return bf[{x, y}] = value(x, y);
}

pair<int, int> find_locmin_point(int N, int M) {
    int lx = 1, rx = N;
    while (rx - lx > 0) {
        int x = (lx + rx) / 2;

        int ly = 1, ry = M;
        while (ry - ly > 0) {
            int m1 = (ly + ry) / 2;
            int m2 = (ly + ry) / 2 + 1;

            if (get(x, m1) <= get(x, m2)) {
                ry = m1;
            }
            else {
                ly = m2;
            }
        }

        if (x > 1 && get(x - 1, ly) < get(x, ly)) {
            rx = x - 1;
        }
        else if (x < N && get(x + 1, ly) < get(x, ly)) {
            lx = x + 1;
        }
        else {
            lx = rx = x;
        }
    }

    int ly = 1, ry = M;
    while (ry - ly > 0) {
        int m1 = (ly + ry) / 2;
        int m2 = (ly + ry) / 2 + 1;

        if (get(lx, m1) <= get(lx, m2)) {
            ry = m1;
        }
        else {
            ly = m2;
        }
    }

    return { lx, ly };
}
