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

using namespace std;

pair<int, long long> getRowMin(int l, int c1, int c2)
{
	int best = c1;
	long long mini = value(l, c1);
	for (int j = c1+1; j <= c2; j++) {
		long long cand = value(l, j);
		if (cand < mini) {
			mini = cand;
			best = j;
		}
	}
	return {best, mini};
}

pair<int, long long> getColMin(int c, int l1, int l2)
{
	int best = l1;
	long long mini = value(l1, c);
	for (int i = l1+1; i <= l2; i++) {
		long long cand = value(i, c);
		if (cand < mini) {
			mini = cand;
			best = i;
		}
	}
	return {best, mini};
}

pair<int, int> solve(int l1, int l2, int c1, int c2)
{
	if (l1 == l2 && c1 == c2) {
		return {l1, c1};
	}
	if (l2-l1 < c2-c1) {
		int mij = (c1+c2)/2;
		auto [poz, val] = getColMin(mij, l1, l2);
		if (mij > c1 && value(poz, mij-1) < val) {
			return solve(l1, l2, c1, mij-1);
		}
		if (mij < c2 && value(poz, mij+1) < val) {
			return solve(l1, l2, mij+1, c2);
		}
		return {poz, mij};
	}
	int mij = (l1+l2)/2;
	auto [poz, val] = getRowMin(mij, c1, c2);
	if (mij > l1 && value(mij-1, poz) < val) {
		return solve(l1, mij-1, c1, c2);
	}
	if (mij < l2 && value(mij+1, poz) < val) {
		return solve(mij+1, l2, c1, c2);
	}
	return {mij, poz};
}

pair<int, int> find_locmin_point(int N, int M) {
    return solve(1, N, 1, M);
}
