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

using namespace std;

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

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

pair<int, int> solve(int lx, int rx, int ly, int ry) {
    if (rx - lx == 1 && ry - ly == 1) {
        return { lx, ly };
    }
    if (rx - lx < ry - ly) {
        int my = (ly + ry) / 2;

        int mn = lx;
        for (int i = lx; i < rx; ++i) {
            if (get(mn, my) > get(i, my)) {
                mn = i;
            }
        }

        if (my - 1 >= ly && get(mn, my - 1) < get(mn, my)) {
            return solve(lx, rx, ly, my);
        }
        if (my + 1 < ry && get(mn, my + 1) < get(mn, my)) {
            return solve(lx, rx, my + 1, ry);
        }
        return { mn, my };
    }
    else {
        int mx = (lx + rx) / 2;

        int mn = ly;
        for (int i = ly; i < ry; ++i) {
            if (get(mx, mn) > get(mx, i)) {
                mn = i;
            }
        }

        if (mx - 1 >= lx && get(mx - 1, mn) < get(mx, mn)) {
            return solve(lx, mx, ly, ry);
        }
        if (mx + 1 < rx && get(mx + 1, mn) < get(mx, mn)) {
            return solve(mx + 1, rx, ly, ry);
        }
        return { mx, mn };
    }
}

pair<int, int> find_locmin_point(int N, int M) {
    pair<int, int> res = solve(0, N, 0, M);
    res.first++;
    res.second++;
    return res;
}
