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

#define f first
#define s second
#define elif else if

using namespace std;

const int N = 500 + 9;
const pair <int, int> rw[2] = {{0, -1}, {0, 1}};
const pair <int, int> cl[2] = {{-1, 0}, {1, 0}};
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int n, m, a[N][N];

int get(int i, int j) {
    if (a[i][j] == 0)
        a[i][j] = value(i + 1, j + 1);
    return a[i][j];
}

pair <int, int> calcRow(int i, int j) {
    int l = j - 1, r = j + 1;
    while (l >= 0 && a[i][l] == 0)
        --l;
    ++l;
    while (r < m && a[i][r] == 0)
        ++r;
    --r;
    bool rg = (j == r);
    while (l < r) {
        int md = (l + r) / 2;
        if (rg) {
            if (get(i, md) > get(i, r))
                l = md + 1;
            elif (get(i, md) > get(i, md + 1))
                l = md + 1, rg = 0;
            else
                r = md;
        }
        else {
            if (get(i, md + 1) > get(i, l))
                r = md;
            elif (get(i, md) < get(i, md + 1))
                r = md, rg = 1;
            else
                l = md + 1;
        }
    }
    return {i, l};
}

pair <int, int> calcCol(int i, int j) {
    int l = i - 1, r = i + 1;
    while (l >= 0 && a[l][j] == 0)
        --l;
    ++l;
    while (r < n && a[r][j] == 0)
        ++r;
    --r;
    bool dw = (j == r);
    while (l < r) {
        int md = (l + r) / 2;
        if (dw) {
            if (get(md, j) > get(r, j))
                l = md + 1;
            elif (get(md, j) > get(md + 1, j))
                l = md + 1, dw = 0;
            else
                r = md;
        }
        else {
            if (get(md + 1, j) > get(l, j))
                r = md;
            elif (get(md, j) < get(md + 1, j))
                r = md, dw = 1;
            else
                l = md + 1;
        }
    }
    return {l, j};
}

pair <int, int> find_locmin_point(int _n, int _m) {
    n = _n;
    m = _m;
    pair <int, int> p = {0, 0};
    bool ok = 1;
    while (ok) {
        ok = 0;
        for (auto u : rw) {
            u.f += p.f;
            u.s += p.s;
            if (min(u.f, u.s) < 0 || u.f == n || u.s == m)
                continue;
            if (get(u.f, u.s) < get(p.f, p.s)) {
                p = calcRow(u.f, u.s);
                ok = 1;
                break;
            }
        }
        if (ok)
            continue;
        for (auto u : cl) {
            u.f += p.f;
            u.s += p.s;
            if (min(u.f, u.s) < 0 || u.f == n || u.s == m)
                continue;
            if (get(u.f, u.s) < get(p.f, p.s)) {
                p = calcCol(u.f, u.s);
                ok = 1;
                break;
            }
        }
    }
    ++p.f;
    ++p.s;
    return p;
}
