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

long long A[505][505], MM, NN;

pair<int, int> divide_and_conquer(int x1, int y1, int x2, int y2){
    if(x1 > x2 || y1 > y2 || x1 < 1 || x1 > NN || y1 < 1 || y1 > MM || x2 < 1 || x2 > NN || y2 < 1 || y2 > MM) return {-1, -1};
    if(x1 == x2 && y1 == y2){
        int mx = x1, my = y1;
        long long val_mid = (A[mx][my] == 0 ? A[mx][my] = value(mx, my) : A[mx][my]);
        long long val_up = (mx - 1 >= 1 ? A[mx - 1][my] == 0 ? A[mx - 1][my] = value(mx - 1, my) : A[mx - 1][my] : 2e18);
        long long val_down = (mx + 1 <= NN ? A[mx + 1][my] == 0 ? A[mx + 1][my] = value(mx + 1, my) : A[mx + 1][my] : 2e18);
        long long val_left = (my - 1 >= 1 ? A[mx][my - 1] == 0 ? A[mx][my - 1] = value(mx, my - 1) : A[mx][my - 1] : 2e18);
        long long val_right = (my + 1 <= MM ? A[mx][my + 1] == 0 ? A[mx][my + 1] = value(mx, my + 1) : A[mx][my + 1] : 2e18);
        if(val_mid < val_up && val_mid < val_down && val_mid < val_left && val_mid < val_right){
            return {mx, my};
        }
        return {-1, -1};
    }
    int mx = (x1 + x2) / 2;
    int my = (y1 + y2) / 2;
    long long val_mid = (A[mx][my] == 0 ? A[mx][my] = value(mx, my) : A[mx][my]);
    long long val_up = (mx - 1 >= 1 ? A[mx - 1][my] == 0 ? A[mx - 1][my] = value(mx - 1, my) : A[mx - 1][my] : 2e18);
    long long val_down = (mx + 1 <= NN ? A[mx + 1][my] == 0 ? A[mx + 1][my] = value(mx + 1, my) : A[mx + 1][my] : 2e18);
    long long val_left = (my - 1 >= 1 ? A[mx][my - 1] == 0 ? A[mx][my - 1] = value(mx, my - 1) : A[mx][my - 1] : 2e18);
    long long val_right = (my + 1 <= MM ? A[mx][my + 1] == 0 ? A[mx][my + 1] = value(mx, my + 1) : A[mx][my + 1] : 2e18);
    if(val_mid < val_up && val_mid < val_down && val_mid < val_left && val_mid < val_right){
        return {mx, my};
    }
    pair<int,int> res = {-1, -1};
    res = divide_and_conquer(x1, y1, mx - 1, my - 1);
    if(res.first == -1) res = divide_and_conquer(mx - 1, my + 1, x1, y2);
    if(res.first == -1) res = divide_and_conquer(mx + 1, my + 1, x2, y2);
    if(res.first == -1) res = divide_and_conquer(mx + 1, y1, x2, my - 1);
    if(res.first == -1 && val_mid > val_up) res = divide_and_conquer(x1, my, mx - 1, my);
    if(res.first == -1 && val_mid > val_down) res = divide_and_conquer(mx + 1, my, x2, my);
    if(res.first == -1 && val_mid > val_left) res = divide_and_conquer(mx, y1, mx, my - 1);
    if(res.first == -1 && val_mid > val_up) res = divide_and_conquer(mx, my + 1, mx, y2);
    return res;
}

pair<int, int> find_locmin_point(int N, int M) {
    MM = M;
    NN = N;
    pair<int,int> res = divide_and_conquer(1, 1, N, M);
    assert(res.first != -1);
    return res;
}
