#include<bits/stdc++.h>
using namespace std;
#define ll long long
#include "richest.h"
int n;
const int a[]={500000, 250000, 125000, 62500, 20833, 3472, 183, 1};
int ct1[1000005], ct2[1000005];
void solve(vector<int> &vc, int k){
	vector<int> tp=vc; 
	int m=vc.size();
	for(auto x:vc){
		ct1[x]=ct2[x]=0;
	}
	int p1=m/k, p2=m/k+1, q1=k-m%k, q2=m%k;
	assert(p1*q1+p2*q2==m);
	cerr << m << ' ' << k << '\n';
	vector<int> v1, v2;
	for(int i=1; i<=q1; ++i){
		vector<int> tp;
		for(int j=1; j<=p1; ++j){
			tp.push_back(vc.back());
			vc.pop_back();
		}
		for(auto p:tp){
			for(auto q:tp){
				if(p<q){
					ct1[p]++, ct1[q]++;
					v1.push_back(p);
					v2.push_back(q);
				}
			}
		}
	}
	for(int i=1; i<=q2; ++i){
		vector<int> tp;
		for(int j=1; j<=p2; ++j){
			tp.push_back(vc.back());
			vc.pop_back();
		}
		for(auto p:tp){
			for(auto q:tp){
				if(p<q){
					ct1[p]++, ct1[q]++;
					v1.push_back(p);
					v2.push_back(q);
				}
			}
		}
	}
	vector<int> res=ask(v1, v2);
	for(auto x:res){
		ct2[x]++;
	}
	vector<int> nvc;
	for(auto x:tp){
		assert(ct1[x]>=ct2[x]);
		if(ct1[x]==ct2[x]){
			nvc.push_back(x);
		}
	}
	swap(vc, nvc);
}
int ct[1005];
int richest(int N, int T, int S) {
   	n=N;
   	if(n==1000){
   		vector<int> p1, p2;
   		for(int i=0; i<n; ++i){
   			for(int j=i+1; j<n; ++j){
   				p1.push_back(i);
   				p2.push_back(j);
			}	
		}
		memset(ct, 0, sizeof(ct));
		vector<int> res=ask(p1, p2);
		for(auto x:res){
			ct[x]++;
		}
		for(int i=0; i<n; ++i){
			if(ct[i]==n-1) return i;
		}
	}else{
		vector<int> vc;
		for(int i=0; i<n; ++i){
			vc.push_back(i);
		}
		for(int i=0; i<8; ++i){
			solve(vc, a[i]);
		}
		return vc[0];
	}
	return -1;
}