#include "locmin.h"
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

using ll = long long;

constexpr ll MAXVAL = 1e18;
constexpr int MAXN = 500;
constexpr int MAXM = 500;

int n, m;
ll a[MAXN+2][MAXM+2];

struct Cell
{
	int l, c;
	Cell(int l, int c) : l(l), c(c) {}
	Cell() : l(), c() {}
	bool inBounds(int l1, int l2, int c1, int c2) const
	{
		return l1 <= l && l <= l2 && c1 <= c && c <= c2;
	}
	bool valid() const
	{
		return inBounds(1, n, 1, m);
	}
	long long value() const
	{
		if (!valid()) return MAXVAL+2;
		if (a[l][c]) return a[l][c];
		return a[l][c] = ::value(l, c);
	}
};

int getRowMin(int l, int c1, int c2)
{
	int best = c1;
	ll mini = Cell(l, c1).value();
	for (int j = c1+1; j <= c2; j++) {
		ll cand = Cell(l, j).value();
		if (cand < mini) {
			mini = cand;
			best = j;
		}
	}
	return best;
}

int getColMin(int c, int l1, int l2)
{
	int best = l1;
	ll mini = Cell(l1, c).value();
	for (int i = l1+1; i <= l2; i++) {
		ll cand = Cell(i, c).value();
		if (cand < mini) {
			mini = cand;
			best = i;
		}
	}
	return best;
}

Cell solve(int l1, int l2, int c1, int c2, const Cell &p)
{
	if (l1 == l2 && c1 == c2) {
		return Cell(l1, c1);
	}
	if (l2-l1 < c2-c1) {
		int mij = (c1+c2)/2;
		int poz = getColMin(mij, l1, l2);
		ll val = Cell(poz, mij).value();
		if (val < p.value()) {
			if (mij > c1 && Cell(poz, mij-1).value() < val) {
				return solve(l1, l2, c1, mij-1, Cell(poz, mij-1));
			}
			if (mij < c2 && Cell(poz, mij+1).value() < val) {
				return solve(l1, l2, mij+1, c2, Cell(poz, mij+1));
			}
			return Cell(poz, mij);
		}
		if (p.inBounds(l1, l2, c1, mij-1)) {
			return solve(l1, l2, c1, mij-1, p);
		}
		return solve(l1, l2, mij+1, c2, p);
	}   
	int mij = (l1+l2)/2;
	int poz = getRowMin(mij, c1, c2);
	ll val = Cell(mij, poz).value();
	if (val < p.value()) {
		if (mij > l1 && Cell(mij-1, poz).value() < val) {
			return solve(l1, mij-1, c1, c2, Cell(mij-1, poz));
		}
		if (mij < l2 && Cell(mij+1, poz).value() < val) {
			return solve(mij+1, l2, c1, c2, Cell(mij+1, poz));
		}
		return Cell(mij, poz);
	}
	if (p.inBounds(l1, mij-1, c1, c2)) {
		return solve(l1, mij-1, c1, c2, p);
	}
	return solve(mij+1, l2, c1, c2, p);
}

pair<int, int> find_locmin_point(int N, int M) {
	n = N;
	m = M;
	if (Cell(1, 1).value() < Cell(2, 1).value() && Cell(1, 1).value() < Cell(1, 2).value()) {
		return {1, 1};
	}
	Cell p = solve(1, n, 1, m, Cell(1, 1));
	return {p.l, p.c};
}
