#include "richest.h"

#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()

int richest(int N, int T, int S) {
        if(N<=1000) {
                vector<int> a,b;
                vector<int> occ(N);
                for(int i=0;i<N;i++)for(int j=i+1;j<N;j++) a.push_back(i),b.push_back(j);
                auto res = ask(a,b);
                for(auto x:res)occ[x]++;
                return max_element(all(occ)) - occ.begin();
        }
        //vector<int> p {2, 2, 2, 2, 5, 10, 20, (int)1e9};
        //vector<int> p {2, 2, 2, 3, 11, 14, 81, (int)1e9};
        vector<int> p{2, 2, 2, 2, 3, 6, 19, (int)1e9};
        vector<int> pos(N);
        for(int i=0;i<N;i++)pos[i]=i;

        for(auto l : p) {
                for(auto x:pos)assert(0<=x&&x<N);
                int n = pos.size();
                l=min(l, n);
                //printf("%d %d\n",n,l);
                if(l==1)break;

                vector<int> a,b;
                for(int z=0;z<n/l;z++) {
                        int i=z*l;
                        for(int j=0;j<l;j++)
                                for(int k=j+1;k<l;k++)
                                        a.push_back(pos[i+j]),b.push_back(pos[i+k]);
                }
                int l2=n%l;
                if(l2>1){
                        int i=n/l*l;
                        for(int j=0;j<l2;j++)
                        for(int k=j+1;k<l2;k++)
                        a.push_back(pos[i+j]),b.push_back(pos[i+k]);
                }


                auto res = ask(a,b);
                vector<int> nx;
                //for(int i=n/l*l;i<n;i++) nx.push_back(pos[i]);

                for(int i=0;i<n/l;i++) {
                        map<int,int> occ;
                        for(int j=0;j<l*(l-1)/2;j++)
                                occ[res[i*l*(l-1)/2+j]]++;
                        int mx=-1;
                        for(auto [x,y]:occ)if(y==l-1)mx=x;
                        assert(mx!=-1);
                        nx.push_back(mx);
                }
                if(l2>1){
                        map<int,int> occ;
                        for(int j=0;j<l2*(l2-1)/2;j++)
                        occ[res[n/l*l*(l-1)/2+j]]++;
                        int mx=-1;
                        for(auto [x,y]:occ)if(y==l2-1)mx=x;
                        assert(mx!=-1);
                        nx.push_back(mx);
                }
                if(l2==1)nx.push_back(pos[n-1]);
                swap(pos,nx);
        }

//for(auto x:pos)printf("%d ",x);
        //printf("return %d\n",pos[0]);
        return pos[0];
}