#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 {row + 1, mid + 1};

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

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

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i][j] == -1)
                a[i][j] = value(i + 1, j + 1);
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            long long Min = inf;
            for (int k = 0; k < 4; k++) {
                int x = i + dx[k], y = j + dy[k];

                if (x < 0 || x > n - 1 || y < 0 || y > m - 1)
                    continue;

                Min = min(Min, a[x][y]);
            }

            if (Min > a[i][j])
                return {i + 1, j + 1};
        }
    }
    
    return {-1, -1};
}