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

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
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 = 1, r = m;
   mat[1][1] = value(1, 1);
   mat[1][m] = value(1, m);

   while (r - l > 1) {
      int mid = (l + r) / 2;
      if (mat[1][mid] == 0) {
         mat[1][mid] = value(1, mid);
      }
      assert(l < mid && mid < r);
      if (mat[1][l] <= mat[1][r] && mat[1][l] <= mat[1][mid]) {
         r = mid;
      } else if (mat[1][r] <= mat[1][l] && mat[1][r] <= mat[1][mid]) {
         l = mid;
      } else {
         if (mat[1][mid + 1] == 0) {
            mat[1][mid + 1] = value(1, mid + 1);
         }
         if (mat[1][mid] < mat[1][mid + 1]) {
            r = mid;
         } else {
            l = mid + 1;
         }
      }
   }

   int ans = r;
   if (mat[1][l] <= mat[1][r]) {
      ans = l;
   }

   if (ans > 1 && mat[1][ans] > value(1, ans - 1)) {
      assert(false);
   }
   if (ans < m && mat[1][ans] > value(1, ans + 1)) {
      assert(false);
   }
   return {1, ans};
}
