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

const int MAXN = 500;

long long mat[MAXN + 5][MAXN + 5];
int cnt[MAXN + 1][MAXN + 1];
int dl[] = { -1 , 0 , 1 , 0 } , dc[] = { 0 , 1 , 0 , -1 };
bool viz[MAXN + 1][MAXN + 1];
struct elem {
    int l , c , val;
    bool operator <( const elem &a ) const {
        if( val == a.val )
            return mat[l][c] > mat[a.l][a.c];
        return val < a.val;

    }
};
struct coord {
    int l , c;
};
priority_queue< elem >pq;
pair< int , int >find_locmin_point( int n , int m ) {
    int l , c , d , st , dr , mij , newl , newc;
    if( n == 1 ) {
        st = 0;
        dr = m + 1;
        mat[1][0] = mat[1][m + 1] = 1e18 + 1;
        while( dr - st > 1 ) {
            mij = ( st + dr ) / 2;
            if( mat[1][mij] == 0 )
                mat[1][mij] = value( 1 , mij );
            if( mat[1][mij + 1] == 0 )
                mat[1][mij + 1] = value( 1 , mij + 1 );
            if( mat[1][mij] < mat[1][mij + 1] )
                dr = mij;
            else
                st = mij;
        }
        return { 1 , dr };
    }
    for( l = 1 ; l <= n ; l++ )
        for( c = 1 ; c <= m ; c++ ) {
            if( l == 1 )
                cnt[l][c]++;
            if( c == 1 )
                cnt[l][c]++;
            if( l == n )
                cnt[l][c]++;
            if( c == m )
                cnt[l][c]++;
        }
    vector< coord >v;
    v.push_back( { 1 , 1 } );
    v.push_back( { 1 , m } );
    v.push_back( { n , 1 } );
    v.push_back( { n , m } );
    for( auto x : v ) {
        l = x.l;
        c = x.c;
        if( mat[l][c] == 0 ) {
            mat[l][c] = value( l , c );
        }
        for( d = 0 ; d < 4 ; d++ ) {
            newl = l + dl[d];
            newc = c + dc[d];
            if( newc == 0 || newl == 0 || newl == n + 1 || newc == m + 1 )
                continue;
            if( mat[l][c] > mat[newl][newc] )
                cnt[newl][newc]++;
            else
                cnt[l][c]++;
            if( cnt[l][c] == 4 )
                 return { l , c };
            if( cnt[newl][newc] == 4 )
                return { newl , newc };
        }
    }
    for( l = 1 ; l <= n ; l++ )
        for( c = 1 ; c <= m ; c++ ) {
            if( mat[l][c] != 0 ) {
                pq.push( { l , c , cnt[l][c] } );
            }
        }
    while( !pq.empty() ) {
        elem k = pq.top();
        if( viz[k.l][k.c] )
            continue;
        viz[k.l][k.c] = 1;
        if( mat[k.l][k.c] == 0 )
            mat[k.l][k.c] = value( k.l , k.c );
        l = k.l;
        c = k.c;
        pq.pop();
        for( d = 0 ; d < 4 ; d++ ) {
            newl = l + dl[d];
            newc = c + dc[d];
            if( newc == 0 || newl == 0 || newl == n + 1 || newc == m + 1 )
                continue;
            mat[newl][newc] = value( newl , newc );
            if( mat[l][c] > mat[newl][newc] )
                cnt[newl][newc]++;
            else
                cnt[l][c]++;
            if( cnt[l][c] == 4 )
                 return { l , c };
            if( cnt[newl][newc] == 4 )
                return { newl , newc };
            pq.push( { newl , newc , cnt[newl][newc] } );
        }
    }
}

