#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, M) < getval(1, M - 1)) return make_pair(1, M);
		 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 = c1 == c2;
		int mnglobal = getval(0, 0), x = 0, y = 0;
		while(l1 < l2 && c1 < c2) {
			// cerr << c1 << ' ' << c2 << '\n';
			if(false) { // && c1 != c2 && (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;
				}
				
				for(int h = -1; h <= 1; h++) 
					if(getval(mid + h, mn) < mnglobal) mnglobal = getval(mid + h, mn), x = mid + h, y = mn;
				if(x == mid && y == mn) return make_pair(x, y);
				if(x < mid) l2 = mid - 1;
				if(x > mid) l1 = mid + 1;
				continue;
			}
			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;
				}
				
				// cerr << atr << '\t' << mn << ' ' << mid << '\n';;
				
				for(int h = -1; h <= 1; h++) 
					if(getval(mn, mid + h) < mnglobal) mnglobal = getval(mn, mid + h), x = mn, y = mid + h;
				if(x == mn && y == mid) return make_pair(x, y);
				if(y < mid) c2 = mid - 1;
				if(y > mid) c1 = mid + 1;
				continue;
			}
		}
		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
