#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include "locmin.h"
#include <random>
#include <cmath>

#define debug(x) #x << " = " << x << '\n'
using ll = long long;
using i128 = __int128;

std::mt19937 rng(123);

const int dx[4] = {-1, 0, +1, 0};
const int dy[4] = {0, -1, 0, +1};
const ll INF = 1e18 + 123;

std::pair<int, int> find_locmin_point(int n, int m) {
    // daca a[1] < a[2] => e gata
    // daca a[n - 1] > a[n] => e gata
    // deci a[1] > a[2] si a[n - 1] < a[n]
    // caut binar mid

    if (n == 1) {
        if (m < 30) {
            std::vector<ll> a(m + 1);
            for (int i = 1; i <= m; i++) {
                a[i] = value(1, i);
            }
            if (a[1] < a[2]) {
                return {1, 1};
            }
            if (a[m] < a[m - 1]) {
                return {1, m};
            }
            for (int i = 2; i < m; i++) {
                if (a[i] < a[i - 1] && a[i] < a[i + 1]) {
                    return {1, i};
                }
            }
        }
        if (value(1, 1) < value(1, 2)) {
            return {1, 1};
        }
        if (value(1, m) < value(1, m - 1)) {
            return {1, m};
        }
        // am cv gen
        // >>><<><<<<>>><<<
        // >       <      <
        int l = 1, r = m;
        while (r - l + 1 >= 3) {
            int mid = (l + r) / 2;
            if (value(1, mid) < value(1, mid + 1)) {
                r = mid;
            } else {
                l = mid;
            }
        }
        return {1, l + 1};
    } else {
        if (n * m < 2026) {
            std::vector<std::vector<ll>> what(n + 2, std::vector<ll>(m + 2, +INF));

            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    what[i][j] = value(i, j);
                }
            }

            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    if (what[i][j] < std::min({what[i - 1][j], what[i][j - 1], what[i + 1][j], what[i][j + 1]})) {
                        return {i, j};
                    }
                }
            }

            assert(false);
        }
        // iau un punct random din matrice
        // ma duc mereu spre cel mai mic vecin

        // iau un punct random
        // merg spre cel mai mic vecin
        // sa zicem ca am vreo n * m lungimea
        // atunci fac ev n * m / 2 pasi
        // daca iau K chestii si sa zicem ca pornesc din a K-a cea mai mica
        // sa zicem ca nimeresc la cam N * M / K pasi
        // deci fac K + 4 * N * M / K >= 2 * sqrt(4 * N * M) = 2 * sqrt(N * M)
        // K = 4 * N * M / K <=> K = sqrt(4 * N * M) <=> K = 2 * sqrt(N * M)

        // K + 4 * N * M / K >= 2 * sqrt(4 * N * M)

        std::pair<int, int> best = {-1, -1};
        ll val = +INF;

        int steps = 2 * std::sqrt(n * m);

        for (int repeat = 0; repeat < steps; repeat++) {
            int x = rng() % n + 1;
            int y = rng() % m + 1;

            ll me = value(x, y);
            if (me < val) {
                val = me;
                best = {x, y};
            }
        }

        auto [x, y] = best;

        while (true) {
            ll mini = val;
            int minX = x, minY = y;

            for (int dir = 0; dir < 4; dir++) {
                int xx = x + dx[dir], yy = y + dy[dir];
                if (1 <= xx && xx <= n && 1 <= yy && yy <= m) {
                    ll v = value(xx, yy);
                    if (v < mini) {
                        mini = v;
                        minX = xx, minY = yy;
                    }
                }
            }

            if (mini < val) {
                x = minX, y = minY;
                val = mini;
            } else {
                break;
            }
        }

        return {x, y};
    }
}

/*

1 7
5 3 5 6 3 9 10



*/
