#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,183},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;
	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;
    		n=x+(y>0);//cout<<n<<" "<<num<<endl;
		}
		//cout<<n<<endl;
		return a[0];
	}
}