#include "richest.h"
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int w[10]={0,2,2,2,2,3,6,19,182},a[N],num,t[N];
void solve(int n,int o){
	//cout<<n<<" "<<o<<endl;
	memset(t,0,sizeof(t));
	int j=w[o];
	vector<int> v1,v2;
	if(5<=o&&o<=7){
		int r=n%j;
		for(int i=0,e=1;i<n;e++){
			
			//if(o==7)cout<<i<<" ";
			int l;if(e<=r)l=j+1;else l=j;
			for(int u=i;u<min(i+l,n);u++)
			for(int v=u+1;v<min(i+l,n);v++)
			v1.push_back(a[u]),v2.push_back(a[v]);
			i+=l;
		}
		//cout<<endl;
		vector<int> v=ask(v1,v2),rr;
		memset(t,0,sizeof(t));
		num=-1;
		for(int o:v)t[o]++;
		for(int i=0,e=1;i<n;e++){
			int l;if(e<=n%j)l=j+1;else l=j;
			for(int u=i;u<i+l;u++)if(t[a[u]]==l-1)rr.push_back(a[u]);
			i+=l;
		}
		for(int o:rr)a[++num]=o;
	}
	else{
		for(int i=0;i<n;){
			for(int u=i;u<min(i+j,n);u++)
			for(int v=u+1;v<min(i+j,n);v++)
			v1.push_back(a[u]),v2.push_back(a[v]);
			i+=j;
		}
		vector<int> v=ask(v1,v2),r;
		memset(t,0,sizeof(t));
		num=-1;
		for(int o:v)t[o]++;
		for(int i=0;i<n;i+=j){
			int w=min(j,n-i);
			for(int u=i;u<i+j;u++)if(t[a[u]]==w-1)r.push_back(a[u]);
		}
		for(int o:r)a[++num]=o;
	}
}

int richest(int N, int T, int S) {
	if(N==1000){
		memset(t,0,sizeof(t));
		vector<int> v1,v2;
		for(int i=0;i<N;i++)
		for(int j=i+1;j<N;j++)
		v1.push_back(i),v2.push_back(j);
		vector<int> v=ask(v1,v2);
		for(int o:v)t[o]++;
		for(int i=0;i<N;i++)if(t[i]==N-1)return i;
	}
    else{
    	int n=N;
    	for(int i=0;i<n;i++)a[i]=i;
    	for(int i=1;i<=8;i++){
    		solve(n,i);
    		int t=w[i];
    		int x=n/t,y=n%t;
    		if(5<=i&&i<=7)n=x;else n=x+(y>0);//cout<<n<<" "<<num<<endl;
		}
		//cout<<n<<endl;
		return a[0];
	}
}