#include "richest.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
int vis[2077][2077],bel[1000007],p[1000005],B,len; 
set<int> s[10];
vector<int> vec[10];
int richest(int N, int T, int S) {
    if(N==1000 && T==1 && S==499500){
        vector<int> a,b,c;
        for(int i=0;i<N;i++){
            for(int j=i+1;j<N;j++){
                a.pb(i),b.pb(j);
            }
        }
        c = ask(a,b);
        for(int i=0;i<c.size();i++){
            int u = a[i],v = b[i],w = c[i];
            if(u == w) vis[u][v] = 1,vis[v][u] = 0;
            else vis[u][v] = 0,vis[v][u] = 1;
        }
        int ans = 0;
        for(int i=0;i<N;i++){
            int ck = 1;
            for(int j=0;j<N;j++){
                if(i==j) continue;
                if(!vis[i][j]) ck = 0;
            }
            if(ck == 1){
                ans = i;
                break;
            }
        }
        return ans;
    }else{
        srand(time(0));
        B = 100000;
        for(int i=0;i<10;i++){
            int l = i*B,r = l+B-1;
            for(int j=l;j<=r;j++) s[i].insert(j),bel[j] = i;
        }
        while(1){
            for(int i=0;i<10;i++) {
                vec[i].clear();
                for(int x:s[i]) vec[i].pb(x);
                random_shuffle(vec[i].begin(),vec[i].end());
            }
            vector<int> a,b,c;
            for(int i=0;i<10;i++){
                for(int j=0;j+1<vec[i].size();j++){
                    int u = vec[i][j],v = vec[i][j+1];
                    a.pb(u),b.pb(v);
                }
            } 
            c = ask(a,b);
            for(int i=0;i<c.size();i++){
                int u = a[i],v = b[i],w = c[i];
                if(u == w) s[bel[b[i]]].erase(b[i]);
                else s[bel[a[i]]].erase(a[i]);
            }
            int chk = 1;
            for(int i=0;i<10;i++) chk = chk&(s[i].size()==1);
            if(chk) break;
        }
        vector<int> f,a,b,c;
        for(int i=0;i<10;i++) f.pb(*s[i].begin());
        for(int i=0;i<10;i++){
            for(int j=i+1;j<10;j++){
                a.pb(f[i]),b.pb(f[j]);
            }
        }
        c = ask(a,b);
        for(int i=0;i<c.size();i++){
            int u = a[i],v = b[i],w = c[i];
            if(u == w) vis[bel[u]][bel[v]] = 1;
            else vis[bel[v]][bel[u]] = 1;
        }
        int ans = 0;
        for(int i=0;i<10;i++){
            int ck = 1;
            for(int j=0;j<10;j++){
                if(i==j) continue;
                if(!vis[i][j]) ck = 0;
            }
            if(ck == 1){
                ans = i;
                break;
            }
        }
        ans = f[ans];
        return ans;
    }
}