#include "code.h"
#include <bits/stdc++.h>
#define MAXN 3010
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define sz(x) int((x).size())
#define PRINT(x) cerr<<#x<<'='<<x<<endl;
#define all(x) begin(x),end(x)
bool kol[MAXN], red[MAXN], kol2[MAXN], red2[MAXN];
int val[MAXN][MAXN], kk;
///PROMENITI RAND AKO RADIS VELIKO!!!!!!
int upit(int i, int j) {
    //PRINT(i);
    //PRINT(j);
    if(val[i][j] != 0) return val[i][j];
    kk--;
    return val[i][j] = Pitaj(i, j);
}
vector<int> rndm;
std::vector<int> Nadji(int N, int K)
{
    kk = K;
    for(int i = 1; i <= N; i++) rndm.pb(i);
    for(int i = 0; i <= N; i++) val[i][0] = -1;
    srand(68201);
    random_shuffle(all(rndm));
    if(K == N*N) {
        for(int k = 1; k <= N; k++) {
            int i = rndm[k-1];
            int maxJ = 0, cnt = 1;
            for(int j = 1; j <= N; j++) {
                if((val[i][j] != 0) + (val[i][maxJ] != 0) > kk) goto kraj;
                if(upit(i, j) > upit(i, maxJ)) maxJ = j, cnt = 1;
                else if(upit(i, j) == upit(i, maxJ)) cnt++;
            }
            if(cnt > 1) continue;
            bool valid = 1;
            for(int j = 1; j <= N; j++) {
                if((val[j][maxJ] != 0) + (val[i][maxJ] != 0) > kk) goto kraj;
                if(i != j && upit(j, maxJ) <= upit(i, maxJ)) {
                    valid = 0; break;
                }
            }
            if(valid) {
                vector<int> q = {i, maxJ};
                return q;
            }
        }
    } else {
        while(kk--) {
            int i, j;
            while(1) {
                i = rand()%N+1;
                j = rand()%N+1;
                if(!(kol[j]&&red[i]) && val[i][j] == 0) break;
            }
            val[i][j] = Pitaj(i, j);
            if(val[i][j] == 1) kol[j] = 1;
            else if(val[i][j] == 3) red[i] = 1;
            else {
                if(red2[i]) red[i] = 1;
                else red2[i] = 1;
                if(kol2[j]) kol[j] = 1;
                else kol2[j] = 1;
            }
        }
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= N; j++) {
                if(!kol[j] && !red[i]) {
                    vector<int> q = {i, j};
                    return q;
                }
            }
        }
    }
    kraj:
        vector<int> q = {0, 0};
        return q;
}