#include<bits/stdc++.h>
#include"locmin.h"
using namespace std;
using ll=long long;

//long long value(int r, int c)

mt19937_64 rng(time(0));
const ll N=555;
ll a[N][N],n,m;

ll ask(ll xx,ll yy){
	return value((int)xx,(int)yy);
}

vector<array<ll,2>>okolo(ll xx,ll yy){
	vector<array<ll,2>>ret;
	if(xx-1>=1&&!a[xx-1][yy])ret.push_back({xx-1,yy});
	if(xx+1<=n&&!a[xx+1][yy])ret.push_back({xx+1,yy});
	if(yy-1>=1&&!a[xx][yy-1])ret.push_back({xx,yy-1});
	if(yy+1<=m&&!a[xx][yy+1])ret.push_back({xx,yy+1});
	return ret;
}

std::pair <int, int> find_locmin_point(int _n, int _m){
	n=_n;
	m=_m;
	a[1][0]=2e18;
	a[1][m+1]=2e18;
	ll l=1,r=m;
	while(l<=r){
		ll md=(l+r)/2;
		for(auto[u,v]:okolo(1,md))a[u][v]=ask(u,v);
		if(a[1][md]<a[1][md-1]&&a[1][md]<a[1][md+1]){
			return{1,(int)md};
		}
		if(a[1][md-1]<a[1][md+1]){
			r=md-1;
		}else
			l=md+1;
	}
	return{1,(int)l};
}