#include "richest.h"
#include<bits/stdc++.h>
using namespace std;
const int k[9]={1000000,500000,250000,125000,62500,20833,3472,183,1};
int richest(int N, int T, int S) {
	if(N==1000&&T==1&&S==499500) {
		vector<int> a,b;
		for(int i=0;i<N;i++) for(int j=i+1;j<N;j++) {
			a.emplace_back(i);
			b.emplace_back(j);
		}
		vector<int> c(ask(a,b)),cnt(N,0);
		for(auto p:c) cnt[p]++;
		for(int i=0;i<N;i++) if(cnt[i]==N-1) return i;
		return 0;
	}
	vector<int> cur(N),a,b,c,cnt(N,0);
	for(int i=0;i<N;i++) cur[i]=i;
	vector<int> nw;
	for(int i=1;i<=8;i++) {
		int len=k[i-1]/k[i],lm=k[i-1]%k[i];
		a.clear(),b.clear(),c.clear();
		for(int j=0,st=0,ed;j<k[i];j++,st=ed) {
			ed=st+len+(j<lm);
			for(int x=st;x<ed;x++) for(int y=x+1;y<ed;y++)
				a.push_back(cur[x]),b.push_back(cur[y]);
		}
		c=ask(a,b);
		for(int j=0,st=0,ed,tot=0;j<k[i];j++,st=ed) {
			ed=st+len+(j<lm);
			for(int x=st;x<ed;x++) for(int y=x+1;y<ed;y++)
				cnt[c[tot++]]++;
			for(int x=st;x<ed;x++) {
				if(cnt[cur[x]]==ed-st-1) nw.push_back(cur[x]);
				cnt[cur[x]]=0;
			}
		}
		cur=nw;nw.clear();
	}
	return cur[0];
}