#include <bits/stdc++.h>
#include "locmin.h"
using namespace std;

const int MAXN = 505;

long long mat[MAXN][MAXN];
int cnt[MAXN][MAXN];
bool viz[MAXN][MAXN];
int dl[] = { -1 , 0 , 1 , 0 } , dc[] = { 0 , 1 , 0 , -1 };
struct elem {
    int l, c, val;
    bool operator <(const elem &a) const {
        if (val == a.val)
            return mat[l][c] > mat[a.l][a.c];
        return val < a.val;
    }
};
struct coord {
    int l, c;
};
priority_queue<elem> pq;
pair<int, int> find_locmin_point(int n, int m) {
    while (!pq.empty()) pq.pop();
    for (int i = 0; i <= n + 1; i++) {
        for (int j = 0; j <= m + 1; j++) {
            mat[i][j] = 0;
            cnt[i][j] = 0;
            viz[i][j] = false;
        }
    }
    int l, c, d, st, dr, mij, newl, newc;
    if (n == 1) {
        st = 1; dr = m;
        while (st < dr) {
            mij = st + (dr - st) / 2;
            long long v1 = value(1, mij);
            long long v2 = value(1, mij + 1);
            if (v1 < v2) dr = mij;
            else st = mij + 1;
        }
        return { 1, st };
    }
    for (l = 1; l <= n; l++) {
        for (c = 1; c <= m; c++) {
            if (l == 1) cnt[l][c]++;
            if (c == 1) cnt[l][c]++;
            if (l == n) cnt[l][c]++;
            if (c == m) cnt[l][c]++;
        }
    }
    vector<coord> corners = { {1, 1}, {1, m}, {n, 1}, {n, m} };
    for (auto x : corners) {
        l = x.l; c = x.c;
        if (mat[l][c] == 0) mat[l][c] = value(l, c);
        for (d = 0; d < 4; d++) {
            newl = l + dl[d]; newc = c + dc[d];
            if (newc < 1 || newl < 1 || newl > n || newc > m) continue;
            if (mat[newl][newc] == 0) mat[newl][newc] = value(newl, newc);
            if (mat[l][c] > mat[newl][newc]) cnt[newl][newc]++;
            else cnt[l][c]++;
            if (cnt[l][c] == 4) return { l, c };
            if (cnt[newl][newc] == 4) return { newl, newc };
        }
    }
    for (l = 1; l <= n; l++)
        for (c = 1; c <= m; c++)
            if (mat[l][c] != 0) pq.push({ l, c, cnt[l][c] });
    while (!pq.empty()) {
        elem k = pq.top();
        pq.pop();
        if (viz[k.l][k.c]) continue;
        viz[k.l][k.c] = 1;
        if (k.val < cnt[k.l][k.c]) {
            pq.push({k.l, k.c, cnt[k.l][k.c]});
            viz[k.l][k.c] = 0;
            continue;
        }
        l = k.l; c = k.c;
        for (d = 0; d < 4; d++) {
            newl = l + dl[d]; newc = c + dc[d];
            if (newc < 1 || newl < 1 || newl > n || newc > m) continue;

            if (mat[newl][newc] == 0) {
                mat[newl][newc] = value(newl, newc);
                for(int d2=0; d2<4; d2++) {
                    int vL = newl + dl[d2], vC = newc + dc[d2];
                    if(vL < 1 || vL > n || vC < 1 || vC > m || mat[vL][vC] == 0) continue;
                    if(mat[newl][newc] > mat[vL][vC]) cnt[vL][vC]++;
                    else cnt[newl][newc]++;
                }
                pq.push({newl, newc, cnt[newl][newc]});
            }

            if (cnt[l][c] == 4) return { l, c };
            if (cnt[newl][newc] == 4) return { newl, newc };
        }
    }
    return {1, 1};
}
