#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]; 
bool vis[1000005];
int richest(int n,int t,int s){
	mt19937 rd(time(NULL));
	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);
		vector<int> v1,v2;
		vector<vector<int> > vv;
		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((ti==5||ti==6||ti==4)&&i+Lis[ti]>vec.size()){
				for(int j=0;j<num.size();j++){
					vv[j].push_back(num[j]);
				}
				break;
			}
			vv.push_back(num);
		}
		for(auto num:vv){
			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
*/