#include "richest.h"
#include<bits/stdc++.h>
using namespace std;
const int N=1000005,M=1005;
int lim[20]={0,500000,250000,125000,62496,20832,3472,183,1};
vector <int> qx,qy,qres;
int cnt[N];
int work1()
{
    qx.clear();qy.clear();qres.clear();
    int n=1000;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++) qx.push_back(i-1),qy.push_back(j-1);
    qres=ask(qx,qy);
    for(int i=0;i<n;i++) cnt[i]=0;
    for(int i=0;i<qres.size();i++) cnt[qres[i]]++;
    for(int i=0;i<n;i++) if(cnt[i]==n-1) return i;
}
int a[N],pos[N];
void upd(int l,int r)
{
    for(int i=l;i<=r;i++)
        for(int j=i+1;j<=r;j++) qx.push_back(a[i]),qy.push_back(a[j]);
}
int getmx(int l,int r)
{
    for(int i=l;i<=r;i++) if(cnt[a[i]]==r-l) return a[i];
}
int solve(vector <int> hav,int dep)
{
    int n=hav.size();
    if(n==1) return hav[0];
    for(int i=1;i<=n;i++) a[i]=hav[i-1];
    vector <int> nxt;
    int m=lim[dep];
    // cerr<<n<<' '<<m<<'\n';
    int B=n/m,les=n%m;
    qx.clear();qy.clear();qres.clear();
    for(int i=0;i<hav.size();i++) cnt[hav[i]]=0;
    int now=1;
    for(int i=1;i<=les;i++) upd(now,now+B),now+=B+1;
    for(int i=les+1;i<=m;i++) upd(now,now+B-1),now+=B;
    qres=ask(qx,qy);
    for(int i=0;i<qres.size();i++) cnt[qres[i]]++;
    now=1;
    for(int i=1;i<=les;i++) nxt.push_back(getmx(now,now+B)),now+=B+1;
    for(int i=les+1;i<=m;i++) nxt.push_back(getmx(now,now+B-1)),now+=B;
    return solve(nxt,dep+1);
}
int work2()
{
    int n=1000000;
    vector <int> hav;
    for(int i=1;i<=n;i++) hav.push_back(i-1);
    return solve(hav,1);
}
int richest(int N,int T,int S)
{
    if(N==1000) return work1();
    if(N==1000000) return work2();
}