#include "locmin.h"
#include "bits/stdc++.h"
using std::vector;
using std::min;
using std::map;
using std::pair;
using namespace std;

std::pair <int, int> find_locmin_point(int N, int M) {
	if(N==1){
		if(M==1)return {1,1};
		if(M==2){
			if(value(1,1)<value(1,2))
				return {1,1};
			return {1,2};
		}else if(M==3){
			int a=value(1,1);
			int b=value(1,2);
			int c=value(1,3);
			if(a<b)return {1,1};
			if(c<b)return {1,3};
			return {1,2};
		}
		long long a=value(1,1);
		long long b=value(1,2);
		long long c=value(1,M-1);
		long long d=value(1,M);
		if(b>a)return {1,1};
		if(c>d)return {1,M};
		int bs=-1;
		for(int l=2,r=M;l<=r;){
			int mi=(l+r)>>1;
			if(value(1,mi-1)<value(1,mi)){
				bs=mi-1,r=mi-1;
			}
			else l=mi+1;
		}
		return {1,bs};
	}else{
		queue<pair<int,int>>q;
		q.push({1,1});
		while(not q.empty()){
			auto u=q.front();
			q.pop();
			int dx[]={-1,0,0,1};
			int dy[]={0,-1,1,0};
			long long mn=LLONG_MAX;
			int s=-1;
			int i=u.first,j=u.second;
			for(int k=0;k<4;k++){
				int ti=i+dx[k],tj=j+dy[k];
				if(0<=ti&&ti<N&&0<=tj&&tj<M){
					long long a=value(ti,tj);
					if(a<mn)mn=a,s=k;
				}
			}
			if(s==-1)return{i+1,j+1};
			q.push({i+dx[s],j+dy[s]});
		}
		return {1,1};
	}
}
