#include<iostream>
#include<assert.h>
#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];
    known[r][c]=value(r+1,c+1);
    assert((1<=known[r][c])&&(known[r][c]<=1e18));
    return known[r][c];
}
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};
}
pair <int, int> find_locmin_point (int n, int m) {
    assert((1<=n)&&(n<=MAXN));
    assert((1<=m)&&(m<=MAXN));
    ::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);
    for (;;) {
        /*for (int i=r1; i<=r2; i++) {
            for (int j=c1; j<=c2; j++) {
                cout << query(i,j) << " ";
            }
            cout << endl ;
        }
        cout << endl ;
        cout << r1+1 << " " << r2+1 << " " << c1+1 << " " << c2+1 << endl ;*/
        int midr=(r1+r2)/2,midc=(c1+c2)/2;
        long long int min1=1e18;
        int row,col;
        for (int i=c1; i<=c2; i++) {
            if (min1>query(midr,i)) {
                min1=query(midr,i);
                row=midr; col=i;
            }
            //cout << query(midr,i) << " ";
        }
        //cout << endl << endl ;
        for (int i=r1; i<=r2; i++) {
            if (min1>query(i,midc)) {
                min1=query(i,midc);
                row=i; col=midc;
            }
            //cout << query(i,midc) << " ";
        }
        //cout << endl ;
        //cout << r1 << " " << r2 << " " << c1 << " " << c2 << "  " << row << " " << col << endl ;
        if (row==midr) {
            if ((r1<=row-1)&&(query(row-1,col)<min1)) {
                r2=row-1;
                if (col<midc) c2=midc-1;
                else c1=midc+1;
            }
            else if ((row+1<=r2)&&(query(row+1,col)<min1)) {
                r1=row+1;
                if (col<midc) c2=midc-1;
                else c1=midc+1;
            }
            else return {row+1, col+1};
        }
        else {
            if ((c1<=col-1)&&(query(row,col-1)<min1)) {
                c2=col-1;
                if (row<midr) r2=midr-1;
                else r1=midr+1;
            }
            else if ((col+1<=c2)&&(query(row,col+1)<min1)) {
                c1=col+1;
                if (row<midr) r2=midr-1;
                else r1=midr+1;
            }
            else return {row+1, col+1};
        }
    }
}
