#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[100];
#define ls (now<<1)
#define rs (now<<1|1)
#define mid ((l+r)>>1)
void build(int now,int l,int r){
	vec[dep[now]].push_back(now);
	tree[now]=-1;
	if(l==r){
		tree[now]=l;
		return ;
	}
	dep[ls]=dep[now]+1;
	dep[rs]=dep[now]+1;
	build(ls,l,mid);
	build(rs,mid+1,r);
}
#undef ls
#undef rs
#undef mid
int richest(int n,int t,int s){
	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;
		}
	}
	build(1,0,n-1);
	for(int i=20;i>=8;i--){
		vector<int> v1,v2,id;
		for(int u:vec[i]){
			if(tree[u]==-1){
				v1.push_back(tree[u<<1]);
				v2.push_back(tree[u<<1|1]);
				id.push_back(u);
			}
		}
		if(v1.size()==0) continue;
		vector<int> ret=ask(v1,v2);
		for(int j=0;j<id.size();j++){
			tree[id[j]]=ret[j];
		}
	}
	vector<int> v1,v2;
	for(int i=0;i<vec[8].size();i++){
		for(int j=0;j<i;j++){
			v1.push_back(tree[vec[8][i]]);
			v2.push_back(tree[vec[8][j]]);
		}
	}
	vector<int> ret=ask(v1,v2);
	for(int u:ret) a[u]++;
	int pos=0;
	for(int i=1;i<n;i++){
		if(a[i]>=a[pos]) pos=i;
	}
	for(int i=0;i<n;i++) a[i]=0;
	for(int i=0;i<=20;i++) vec[i].clear();
	return pos;
}
/*
g++ grader.cpp richest.cpp -o richest.exe -O2 -std=c++14 -static
*/