#include <bits/stdc++.h>
#include "code.h"
#define maxN 3010

using namespace std;

int r[maxN], c[maxN], mr[maxN], mc[maxN], q=0, I, J, h, pr, pc, good;
int H[maxN][maxN];
bool moze[maxN][maxN];
vector<int> out;

void f(int i, int j)
{
    if (!moze[i][j]) return;
    moze[i][j] = false;
    r[i]--;
    c[j]--;
    good--;
    //cout << good << " ";
}

void check(int i, int j)
{
    if (mr[i] >= mc[j]) f(i, j);
}

std::vector<int> Nadji1(int N, int K)
{
    q = N;
    good = N*N;

    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j)
            moze[i][j] = true;

    for (int i = 1; i <= N; ++i)
        r[i] = c[i] = N;

    for (int i = 1; i <= N; ++i)
    {
        mr[i] = mc[i] = Pitaj(i, i);
        H[i][i] = mr[i];
    }

    for (int i = 1; i <= N; ++i)
        for (int j = i+1; j <= N; ++j)
        {
            check(i, j);
            check(j, i);
        }
    //cout << endl;
    //for (int i = 1; i <= N; ++i) cout << r[i] << " ";
    //cout << endl;
    //for (int i = 1; i <= N; ++i) cout << c[i] << " ";
    //cout << endl;

    while (good > 1)
    {
        I = 1;
        for (int i = 2; i <= N; ++i)
            if (r[i] > r[I])
                I = i;
        J = -1;
        for (int i = 1; i <= N; ++i)
            if (H[I][i] == 0 && (J == -1 || c[i] > c[J]))
                J = i;
        //cout << I << " " << J << endl;
        H[I][J] = Pitaj(I, J);
        if (H[I][J] <= mr[I] || H[I][J] >= mc[J])
            f(I, J);
        if (H[I][J] >= mr[I]) f(I, I);
        if (H[I][J] <= mc[J]) f(J, J);
        mr[I] = max(H[I][J], mr[I]);
        mc[J] = max(H[I][J], mc[J]);
        for (int k = 1; k <= N; ++k)
        {
            if (k == I || k == J) continue;
            check(k, J);
            check(I, k);
        }
        //cout << endl;
        //for (int i = 1; i <= N; ++i) cout << r[i] << " ";
        //cout << endl;
        //for (int i = 1; i <= N; ++i) cout << c[i] << " ";
        //cout << endl;
    }

    //if (good < 0) cerr << "-1";
    if (good == 0)
    {
        out.push_back(0);
        out.push_back(0);
        return out;
    }

    for (int i = 1; i <= N; ++i)
    {
        if (r[i] == 1) I = i;
        if (c[i] == 1) J = i;
    }

    //cout << " " << I << " " << J << endl;

    for (int i = 1; i <= N; ++i)
    {
        if (i == I) continue;
        if (H[i][J] != 0) continue;
        if (Pitaj(i, J) <= H[I][J])
        {
            out.push_back(0);
            out.push_back(0);
            return out;
        }
    }

    for (int j = 1; j <= N; ++j)
    {
        if (j == J) continue;
        if (H[I][j] != 0) continue;
        if (Pitaj(I, j) >= H[I][J])
        {
            out.push_back(0);
            out.push_back(0);
            return out;
        }
    }

    out.push_back(I);
    out.push_back(J);
    return out;
}

vector<int> Nadji2(int N, int K)
{
    for (int i = 1; i <= N; ++i)
    {
        mc[i] = 1000000010;
    }
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j)
            H[i][j] = Pitaj(i, j);
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j)
        {
            if (H[i][j] > mr[i])
                mr[i] = H[i][j];
            else if (H[i][j] == mr[i]) mr[i]++;
            if (H[i][j] < mc[j])
                mc[j] = H[i][j];
            else if (H[i][j] == mc[j]) mc[j]--;
        }
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j)
            if (mr[i] == H[i][j] && mc[j] == H[i][j])
            {
                out.push_back(i);
                out.push_back(j);
                return out;
            }
    out.push_back(0);
    out.push_back(0);
    return out;
}

vector<int> Nadji(int N, int K)
{
    if (K == 5000) return Nadji1(N, K);
    return Nadji2(N, K);
}