#include <bits/stdc++.h>
#include <experimental/random>
#include "locmin.h"

using namespace std;
pair<long long,long long>vec[5];
vector<pair<pair<long long,long long>,long long>>v;
long long mat[505][505];
long long ver(long long i,long long j,long long n,long long m)
{
    if(i<1||i>n)
        return 0;
    if(j<1||j>m)
        return 0;
    return 1;
}
pair<int,int>find_locmin_point(int N,int M)
{
    vec[0]= {-1,0};
    vec[1]= {1,0};
    vec[2]= {0,1};
    vec[3]= {0,-1};
    long long i1=1,j1=1,valant;
    while(1)
    {
        v.clear();
        i1=std::experimental::randint(1,N);
        j1=std::experimental::randint(1,M);
        if(mat[i1][j1])
            valant=mat[i1][j1];
        else valant=value(i1,j1);
        mat[i1][j1]=valant;
        for(long long l=0; l<4; l++)
        {
            long long i2=i1+vec[l].first,j2=j1+vec[l].second;
            if(ver(i2,j2,N,M))
            {
                long long val;
                if(mat[i2][j2]==0)
                    val=value(i2,j2);
                else val=mat[i2][j2];
                mat[i2][j2]=val;
                v.push_back({{i2,j2},val});
                if(val<valant)
                    break;
            }
        }
        long long ok=1;
        for(auto it:v)
            if(it.second<valant)
            {
                ok=0;
                break;
            }
        if(ok==1)
            return {i1,j1};
    }
}
