#include<bits/stdc++.h>
 #include "richest.h"
using namespace std;
#define endl '\n'
const int cut[]={500000, 250000, 125000, 62500, 20832, 3472, 183, 1};
map<pair<int,int>,int> id;
int richest(int n,int t,int s){
	id.clear();
	if(n==1000){
		vector<int> a,b;
		for(int i=0;i<n;i++)
			for(int j=i+1;j<n;j++)
				a.push_back(i),b.push_back(j),id[{i,j}]=(int)a.size()-1;
		auto p=ask(a,b);
		for(int i=0;i<n;i++){
			bool fl=1;
			for(int j=0;j<n;j++)if(i!=j&&p[id[{min(i,j),max(i,j)}]]!=i){
				fl=0;
				break;
			}
			if(fl)return i;
		}
	}
	vector<int> cur;
	for(int i=0;i<n;i++)cur.push_back(i);
	for(int p=0;p<8;p++){
		vector<int> a,b,tmp;
		int s=(int)cur.size()/cut[p],bmod=(int)cur.size()%cut[p],amod=cut[p]-bmod;
		int top=0;
		for(int i=0;i<amod;i++){
			for(int j=top;j<top+s;j++)
				for(int k=j+1;k<top+s;k++)
					a.push_back(cur[j]),b.push_back(cur[k]),id[{cur[j],cur[k]}]=(int)a.size()-1;
			top+=s;
		}
		for(int i=0;i<bmod;i++){
			for(int j=top;j<=top+s;j++)
				for(int k=j+1;k<=top+s;k++)
					a.push_back(cur[j]),b.push_back(cur[k]),id[{cur[j],cur[k]}]=(int)a.size()-1;
			top+=s+1;
		}
		auto c=ask(a,b);top=0;
		for(int i=0;i<amod;i++){
			int sp=top;
			for(int j=top+1;j<top+s;j++)
				if(c[id[{cur[sp],cur[j]}]]==cur[j])sp=j;
			tmp.push_back(cur[sp]);
			top+=s;
		}
		for(int i=0;i<bmod;i++){
			int sp=top;
			for(int j=top+1;j<=top+s;j++)
				if(c[id[{cur[sp],cur[j]}]]==cur[j])sp=j;
			tmp.push_back(cur[sp]);
			top+=s+1;
		}
		cur=tmp;
	}
	return cur[0];
}