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

using namespace std;

const long long inf = 2e18;

/*vector<vector<long long>> mat;

long long value(int r, int c) {
    return mat[r - 1][c - 1];
}*/

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

pair<int, int> find_locmin_point(int n, int m) {
    if (n == 1) {
        int l = 0, r = m - 1;
        vector<long long> a(m, -1);
        while (l <= r) {
            int mid = (l + r) / 2;


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

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

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

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

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

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

            else
                l = mid + 1;
        }

        return {-1, -1};
    }

    vector<vector<long long>> a(n, vector<long long>(m));
    
    int r = n / 2, c = m / 2;

    while (true) {
        if (a[r][c] == -1)
            a[r][c] = value(r + 1, c + 1);

        pair<int, int> nxt{r, c};
        for (int k = 0; k < 4; k++) {
            int x = r + dx[k], y = c + dy[k];

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

            if (a[x][y] == -1)
                a[x][y] = value(x + 1, y + 1);

            if (a[x][y] > a[nxt.first][nxt.second])
                nxt = {x, y};
        }

        if (nxt.first == r && nxt.second == c)
            return {r + 1, c + 1};

        r = nxt.first, c = nxt.second;
    }

    return {-1, -1};
}