#include<iostream>
#include<algorithm>
#include<vector>
#include "locmin.h"
#define MAXN 500
#define MAXM 500
using namespace std;
long long int known[MAXN][MAXM];
int n,m;
long long int query (int r, int c) {
    if ((r<0)||(r>=n)||(c<0)||(c>=m)) return 1e18;
    if (known[r][c]!=0) return known[r][c];
    return known[r][c]=value(r+1,c+1);
}
pair <int, int> find_1row (int r, int c1, int c2) {
    if (c1==c2) return {r+1, c1+1};
    int mid=(c1+c2)/2;
    if (query(r,mid-1)<query(r,mid)) return find_1row(r,c1,mid-1);
    if (query(r,mid+1)<query(r,mid)) return find_1row(r,mid+1,c2);
    return {r+1, mid+1};
}
pair <int, int> find_1col (int c, int r1, int r2) {
    if (r1==r2) return {r1+1, c};
    int mid=(r1+r2)/2;
    if (query(mid-1,c)<query(mid,c)) return find_1row(c,r1,mid-1);
    if (query(mid+1,c)<query(mid,c)) return find_1row(c,mid+1,r2);
    return {mid+1, c+1};
}
int drow[]={ -1, -0, +0, +1 };
int dcol[]={ -0, -1, +1, +0 };
pair <int, int> find_locmin_point (int n, int m) {
    ::n=n; ::m=m;
    int r1=0,r2=n-1,c1=0,c2=m-1;
    if (n==1) return find_1row(r1,c1,c2);
    if (m==1) return find_1col(c1,r1,r2);
    int r=rand()%n,c=rand()%m;
    //cout << r+1 << " " << c+1 << endl ;
    for (;;) {
        vector <int> dir,other;
        for (int i=0; i<4; i++) {
            int row=r+drow[i],col=c+dcol[i];
            if (query(row,col)<query(r,c)) {
                dir.push_back(i);
            }
            else if (query(row,col)!=1e18) other.push_back(i);
        }
        if (dir.size()==0) return {r+1, c+1};
        random_shuffle(dir.begin(),dir.end());
        random_shuffle(other.begin(),other.end());
        if ((other.size()==0)||(rand()%2==0)) {
            r+=drow[dir.front()]; c+=dcol[dir.front()];
        }
        else {
            r+=drow[other.front()]; c+=dcol[other.front()];
        }
    }
}
