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

using namespace std;

mt19937 rng(68);
int rrng(int l, int r) {
   int x = rng();
   x = abs(x);
   return l + x % (r - l + 1);
}

const int N = 505;
using ll = long long;
ll mat[N][N];
int nl[] = {0, -1, 0, 1};
int nc[] = {1, 0, -1, 0};

int n, m;

bool inbound(int l, int c) {
   if (l <= 0 || c <= 0 || l > n || c > m) {
      return false;
   }
   return true;
}

pair<int, int> find_locmin_point(int _n, int _m) {
   n = _n;
   m = _m;
   int l = rrng(1, n);
   int c = rrng(1, m);
   mat[l][c] = value(l, c);

   for (int i = 0; i < 200; i ++) {
      int ll = rrng(1, n);
      int cc = rrng(1, m);
      if (mat[ll][cc] == 0) {
         mat[ll][cc] = value(ll, cc);
         if (mat[ll][cc] < mat[l][c]) {
            l = ll;
            c = cc;
         }
      }
   }

   while (1) {
      bool ok = false;
      vector<int> vec(4);
      for (int i = 0; i < 4; i ++) {
         vec[i] = i;
      }
      shuffle(vec.begin(), vec.end(), rng);
      for (auto i : vec) {
         int ll = l + nl[i];
         int cc = c + nc[i];
         if (!inbound(ll, cc)) {
            continue;
         }
         if (mat[ll][cc] == 0) {
            mat[ll][cc] = value(ll, cc);
         }
         if (mat[l][c] > mat[ll][cc]) {
            l = ll;
            c = cc;
            ok = true;
            break;
         }
      }
      if (!ok) {
         return {l, c};
      }
   }
}
