#include"richest.h"
#include<bits/stdc++.h>
using namespace std;
int tii[1005][1005];
int tree[1000005<<2],dep[1000005<<2];
int a[1000005];
vector<int> vec;
bool del[1000005]; 
int richest(int n,int t,int s){
	mt19937 rd(210);
	if(n==1000){
		vector<int> v1,v2;
		for(int i=0;i<n;i++){
			for(int j=0;j<i;j++){
				v1.push_back(i);
				v2.push_back(j);
			}
		}
		vector<int> ret=ask(v1,v2);
		for(int i=0;i<v1.size();i++){
			tii[v1[i]][v2[i]]=tii[v2[i]][v1[i]]=ret[i];
		}
		for(int i=0;i<n;i++){
			int num=0; 
			for(int j=0;j<n;j++){
				num+=(tii[i][j]==i);
			}
			if(num==n-1) return i;
		}
	}
	for(int i=0;i<n;i++) vec.push_back(i),del[i]=0;
	vector<int> Lis={2,2,2,2,3,6,19,183};
	for(int ti=0;ti<8;ti++){
		shuffle(vec.begin(),vec.end(),rd);
//		cerr<<ti<<" "<<vec.size()<<'\n';
		vector<int> v1,v2;
		for(int i=0;i<vec.size();i+=Lis[ti]){
			vector<int> num;
			for(int j=i;j<vec.size()&&j<i+Lis[ti];j++){
				num.push_back(vec[j]);
			}
			if(vec.size()==183){
//				cerr<<num.back()<<' ';
				del[num.back()]=1;
				num.pop_back();
//				cerr<<num.size()<<' ';
			}
			for(int i=0;i<num.size();i++){
				for(int j=0;j<i;j++){
					v1.push_back(num[i]);
					v2.push_back(num[j]);
				}
			}
		}
		vector<int> ret=ask(v1,v2);
		for(int i=0;i<ret.size();i++){
			if(v1[i]==ret[i]){
				del[v2[i]]=1;
			}
			else del[v1[i]]=1;
		}
		vec.clear();
		for(int i=0;i<n;i++){
			if(!del[i]) vec.push_back(i);
		}
	}
	return vec[0];
}
/*
g++ grader.cpp richest.cpp -o richest.exe -O2 -std=c++14 -static
richest.exe
*/