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

vector<vector<long long>> board;
vector<vector<bool>> maybe;
std::pair<int, int> ans;

bool check(int i, int j, int N, int M)
{
    if (!maybe[i][j])
    {
        return false;
    }

    if (board[i][j] == INT_MIN)
    {
        board[i][j] = value(i + 1, j + 1);
    }

    // board[i + 1][j]
    // board[i - 1][j]
    // board[i][j + 1]
    // board[i][j - 1]

    if (i + 1 >= N)
    {
        ;
    }
    else if (board[i + 1][j] == INT_MIN)
    {
        ;
    }
    else if (board[i + 1][j] <= board[i][j])
    {
        maybe[i][j] = false;
        if (check(i + 1, j, N, M))
        {
            return true;
        }
        return false;
    }

    if (i - 1 < 0)
    {
        ;
    }
    else if (board[i - 1][j] == INT_MIN)
    {
        ;
    }
    else if (board[i - 1][j] <= board[i][j])
    {
        maybe[i][j] = false;
        if (check(i - 1, j, N, M))
        {
            return true;
        }
        return false;
    }

    if (j + 1 >= M)
    {
        ;
    }
    else if (board[i][j + 1] == INT_MIN)
    {
        ;
    }
    else if (board[i][j + 1] <= board[i][j])
    {
        maybe[i][j] = false;
        if (check(i, j + 1, N, M))
        {
            return true;
        }
        return false;
    }

    if (j - 1 < 0)
    {
        ;
    }
    else if (board[i][j - 1] == INT_MIN)
    {
        ;
    }
    else if (board[i][j - 1] <= board[i][j])
    {
        maybe[i][j] = false;
        if (check(i, j - 1, N, M))
        {
            return true;
        }
        return false;
    }

    if (i + 1 >= N)
    {
        ;
    }
    else if (board[i + 1][j] == INT_MIN)
    {
        board[i + 1][j] = value(i + 1 + 1, j + 1);
        if (board[i + 1][j] <= board[i][j])
        {
            maybe[i][j] = false;
            if (check(i + 1, j, N, M))
            {
                return true;
            }
            return false;
        }
    }

    if (i - 1 < 0)
    {
        ;
    }
    else if (board[i - 1][j] == INT_MIN)
    {
        board[i - 1][j] = value(i - 1 + 1, j + 1);
        if (board[i - 1][j] <= board[i][j])
        {
            maybe[i][j] = false;
            if (check(i - 1, j, N, M))
            {
                return true;
            }
            return false;
        }
    }

    if (j + 1 >= M)
    {
        ;
    }
    else if (board[i][j + 1] == INT_MIN)
    {
        board[i][j + 1] = value(i + 1, j + 1 + 1);
        if (board[i][j + 1] <= board[i][j])
        {
            maybe[i][j] = false;
            if (check(i, j + 1, N, M))
            {
                return true;
            }
            return false;
        }
    }

    if (j - 1 < 0)
    {
        ;
    }
    else if (board[i][j - 1] == INT_MIN)
    {
        board[i][j - 1] = value(i + 1, j - 1 + 1);
        if (board[i][j - 1] <= board[i][j])
        {
            maybe[i][j] = false;
            if (check(i, j - 1, N, M))
            {
                return true;
            }
            return false;
        }
    }

    ans = {i + 1, j + 1};
    return true;
}

std::pair<int, int> find_locmin_point(int N, int M)
{
    board = vector<vector<long long>>(N, vector<long long>(M, INT_MIN));
    maybe = vector<vector<bool>>(N, vector<bool>(M, true));

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (check(i, j, N, M))
            {
                return ans;
            }
        }
    }

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (check(i, j, N, M))
            {
                return ans;
            }
        }
    }

    return {-1, -1};
}
