#include <bits/stdc++.h>
#include "locmin.h"

using namespace std;

mt19937 rng(time(nullptr));

const long long inf = 2e18;

vector<vector<long long>> mat;

vector<int> dx{0, -1, 0, 1};
vector<int> dy{-1, 0, 1, 0};

pair<int, int> find_locmin_point(int n, int m) {
    vector<vector<long long>> a(n, vector<long long>(m, -1));

    int row = 0;

    for (int row = 0; row < n; row++) {
        int l = 0, r = m - 1;
        while (l <= r) {
            int mid = (l + r) / 2;

            if (a[row][mid] == -1)
                a[row][mid] = value(row + 1, mid + 1);

            if (row - 1 >= 0 && a[row - 1][mid] == -1) {
                a[row - 1][mid] = value(row, mid + 1);

                if (a[row - 1][mid] < a[row][mid]) {
                    row--;
                    break;
                }
            }

            if (row + 1 < n && a[row + 1][mid] == -1) {
                a[row + 1][mid] = value(row + 2, mid + 1);

                if (a[row + 1][mid] < a[row][mid]) {
                    row++;
                    break;
                }
            }

            if (mid - 1 >= 0 && a[row][mid - 1] == -1)
                a[row][mid - 1] = value(row + 1, mid);

            if (mid + 1 < m && a[row][mid + 1] == -1)
                a[row][mid + 1] = value(row + 1, mid + 2);

            long long x = (mid - 1 >= 0 ? a[row][mid - 1] : inf);
            long long y = (mid + 1 < m ? a[row][mid + 1] : inf);
            long long z = (row - 1 >= 0 ? a[row - 1][mid] : inf);
            long long w = (row + 1 < n ? a[row + 1][mid] : inf);

            if (min({x, y, z, w}) > a[row][mid])
                return {1, mid + 1};

            else if (x < a[row][mid])
                r = mid - 1;

            else
                l = mid + 1;
        }
        
        row++;
    }

    return {-1, -1};
}