#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,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];
}