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

using namespace std;

#define int long long

int dirx[4] = {-1, 1, 0, 0};
int diry[4] = {0, 0, -1, 1};

const int nmax = 5e2 + 5;
long long mat[nmax][nmax];

std::pair <signed, signed> find_locmin_point(signed N, signed M) {
	for(int i = 0; i <= N + 1; i++) {
		for(int j = 0; j <= M + 1; j++)
			mat[i][j] = -1;
	}
		auto getval = [&](int a, int b) {
			if(a < 1 || a > N || b < 1 || b > M) return ((long long)1e18) + 100000 + 5;
			if(mat[a][b] != -1) return mat[a][b];
			return mat[a][b] = value(a, b);
		};
    if(N == 1) {
		 if(M == 1) return make_pair(1, 1);
		 if(getval(1, 1) < getval(1, 2)) return make_pair(1, 1);
		 if(getval(1, N) < getval(1, N - 1)) return make_pair(1, N);
		 int l = 1, r = M;
		 while(l < r) {
			 int mid = (l + r) >> 1;
			 if(getval(1, mid) > getval(1, mid + 1)) {
				 l = mid;
				 continue;
			 }
			 if(getval(1, mid) > getval(1, mid - 1)) {
				 r = mid;
				 continue;
			 }
			 return make_pair(1, mid);
		 }
		 while(1) cerr << ":)\n";
		 return make_pair(1, 1);
	 }
	 else {
		int l1 = 1, l2 = N, c1 = 1, c2 = M;
		int dir = 0;
		while(l1 < l2 || c1 < c2) {
			if(dir == 0 || l1 == l2) {
				int mid = (l1 + l2) >> 1, tmp;
				int mn = c1, atr = getval(mid, c1);
				for(int j = c1 + 1; j <= c2; j++) {
					auto t = getval(mid, j);
					if(t < atr) atr = t, mn = j;
				}
				if((tmp = getval(mid - 1, mn)) < atr) {
					l2 = mid - 1;
					dir = 1;
					continue;
				}
				if((tmp = getval(mid + 1, mn)) < atr) {
					l1 = mid + 1;
					dir = 1;
					continue;
				}
				return make_pair(mid, mn);
			}
			else {
				int mid = (c1 + c2) >> 1, tmp;
				int mn = l1, atr = getval(l1, mid);
				for(int j = l1 + 1; j <= l2; j++) {
					auto t = getval(j, mid);
					if(t < atr) atr = t, mn = j;
				}
				if((tmp = getval(mn, mid - 1)) < atr) {
					c2 = mid - 1;
					dir = 0;
					continue;
				}
				if((tmp = getval(mn, mid + 1)) < atr) {
					c1 = mid + 1;
					dir = 0;
					continue;
				}
				return make_pair(mn, mid);
			}
		}
		while(!(l1 <= l2 && c1 <= c2));
		for(int i = l1; i <= l2; i++) {
			for(int j = c1; j <= c2; j++) {
				if(getval(i, j) < getval(i + 1, j) && getval(i, j) < getval(i - 1, j) && getval(i, j) < getval(i, j - 1) && getval(i, j) < getval(i, j + 1)) return make_pair(i, j);
			}
		}
	 }
		 while(1) cerr << ":)\n";
	 return make_pair(N, M);
	 
} 
#undef int
