#include "locmin.h"
#include<iostream>
#include<map>
#include<random>
using namespace std;

map<pair<long long, long long>, long long> mp;
long long N, M;

long long get(long long x, long long y) {
    if (x < 0 || y < 0 || x >= N || y >= M) {
        return 1e18;
    }
    if (mp.find({x, y}) != mp.end()) {
        return mp[{x, y}];
    }
    // cout << "! " << x << " " << y + << endl;
    return mp[{x, y}] = value(x + 1, y + 1);
}
long long get2(long long x, long long a) {
    return get(x, a) < get(x, a + 1);
}
mt19937 rnd(10);

pair <long long, long long> find_by_x(long long x) {
    if (get2(x, 0)) {
        return {x, 0};
    }
    if (!get2(x, M - 2)) {
        return {x, M - 1};
    }
    long long L = 0, R = M - 2;
    while (R - L > 1) {
        long long mid = (L + R) / 2;
        if (get2(x, mid)) {
            R = mid;
        } else {
            L = mid;
        }
    }
    return {x, L + 1};
}

pair <long long, long long> find_locmin_point(int N2, int M2) {
    // return {1, 10};
    N = N2;
    M = M2;
    pair<long long, pair<long long, long long>> best = {1000000000000000000, {-1, -1}};
    for (long long i = 0; i < N; i++) {
        auto now = find_by_x(i);
        // cout << now.first << " " << now.second << endl;
        best = min(best, {get(now.first, now.second), now});
    }
    // cout << best.second.first + 1 << " " << best.second.second + 1 << endl;
    return {best.second.first + 1, 1};
}
