#include <bits/stdc++.h>
#include "richest.h"
using namespace std;
typedef long long ll;

/*
500000*2
250000*2
125000*2
62500*2
20832*3 1*4
3471*6 1*7
168*19 14*20
1*182
*/

// 1099947

int cnt[1000010];
vector <int> a,b,c,d,e;
pair<pair<int,int>,pair<int,int> > t[10]={
{{0,0},{0,0}},
{{1,182},{0,0}},
{{168,19},{14,20}},
{{3471,6},{1,7}},
{{20832,3},{1,4}},
{{62500,2},{0,0}},
{{125000,2},{0,0}},
{{250000,2},{0,0}},
{{500000,2},{0,0}}
};
int richest(int n,int T,int S){
	if(n==1000){
		for(int i=0;i<n;i++)
			for(int j=i+1;j<n;j++)
				a.push_back(i),b.push_back(j);
		c=ask(a,b);
		for(int x:c)
			cnt[x]++;
		for(int i=0;i<n;i++)
			if(cnt[i]==n-1)
				return i;
	}
	d.resize(n);
	for(int i=0;i<n;i++)
		d[i]=i;
	for(int i=8;i>0;i--){
		int xc=t[i].first.first,x=t[i].first.second;
		int x1c=t[i].second.first,x1=t[i].second.second;
		int p=0;
		for(int j=0;j<xc;j++){
			for(int k=p;k<p+x;k++)
				for(int l=k+1;l<p+x;l++)
					a.push_back(d[k]),b.push_back(d[l]);
			p+=x;
		}
		for(int j=0;j<x1c;j++){
			for(int k=p;k<p+x1;k++)
				for(int l=k+1;l<p+x1;l++)
					a.push_back(d[k]),b.push_back(d[l]);
			p+=x1;
		}
		c=ask(a,b);
		e.clear();
		
		p=0;
		int pc=0;
		for(int j=0;j<xc;j++){
			for(int i=pc;i<pc+x*(x-1)/2;i++)
				cnt[c[i]]++;
			
			for(int i=p;i<p+x;i++)
				if(cnt[d[i]]==x-1)
					e.push_back(d[i]);
			for(int i=p;i<p+x;i++)
				cnt[d[i]]=0;
			p+=x;
			pc+=x*(x-1)/2;
		}
		for(int j=0;j<x1c;j++){
			for(int i=pc;i<pc+x1*(x1-1)/2;i++)
				cnt[c[i]]++;
			
			for(int i=p;i<p+x1;i++)
				if(cnt[d[i]]==x1-1)
					e.push_back(d[i]);
			for(int i=p;i<p+x1;i++)
				cnt[d[i]]=0;
			p+=x1;
			pc+=x1*(x1-1)/2;
		}
		d=e;
		
		a.clear();b.clear();
	}
	return e[0];
}