#include<bits/stdc++.h>
#include "locmin.h"
using namespace std;
#define MAXN 505

long long matrix[MAXN][MAXN];

std::pair <int, int> find_locmin_point(int N, int M)
{
    if (N==1)
    {
        if (M==1) return {1,1};
        int l=1,r=M;matrix[1][0]=LLONG_MAX;matrix[1][M+1]=LLONG_MAX;
        while (l<=r)
        {
            int mid=(l+r)/2;
            if (matrix[1][mid]==0) matrix[1][mid]=value(1,mid);
            if (matrix[1][mid-1]==0) matrix[1][mid-1]=value(1,mid-1);
            if (matrix[1][mid+1]==0) matrix[1][mid+1]=value(1,mid+1);
            if (matrix[1][mid]<matrix[1][mid-1] and matrix[1][mid]<matrix[1][mid+1]) return {1,mid};
            if (matrix[1][mid-1]<matrix[1][mid+1]) r=mid-1;
            else l=mid+1;
        }
    }
    long long minvalue=LLONG_MAX;int row=-1;
    for (int minrow=1;minrow<=N;minrow++)
    {
        long long val=value(minrow,M/2);
        if (val<minvalue) {minvalue=val;row=minrow;}
    }
    matrix[row][0]=matrix[row][M+1]=LLONG_MAX;
    matrix[row][M/2-1]=value(row,M/2-1);
    matrix[row][M/2+1]=value(row,M/2+1);
    matrix[row][M/2]=minvalue;
    if (matrix[row][M/2]<matrix[row][M/2-1] and matrix[row][M/2]<matrix[row][M/2+1]) return {row,M/2};
    int l,r;
    if (matrix[row][M/2-1]<matrix[row][M/2+1]) {l=1,r=M/2-1;}
    else {l=M/2+1;r=M;}
    while (l<=r)
    {
        int mid=(l+r)/2;
        if (matrix[row][mid]==0) matrix[row][mid]=value(row,mid);
        if (matrix[row][mid-1]==0) matrix[row][mid-1]=value(row,mid-1);
        if (matrix[row][mid+1]==0) matrix[row][mid+1]=value(row,mid+1);
        if (matrix[row][mid]<matrix[row][mid-1] and matrix[row][mid]<matrix[row][mid+1]) return {row,mid};
        if (matrix[row][mid-1]<matrix[row][mid+1]) r=mid-1;
        else l=mid+1;
    }
}