#include <bits/stdc++.h>
#include "richest.h"
using namespace std;
const int N=1e6+10;
int du[N];
int L[N],R[N],Nm[10]={0,500000,250000,125000,62500,20832,3472,183,1};
int richest(int n, int T, int S){
    if(n==1000){
        for(int i=0;i<n;i++)du[i]=0;
        vector<int>a,b;
        for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)a.push_back(i-1),b.push_back(j-1);
        a=ask(a,b);
        for(int x:a)du[x]++;
        for(int i=0;i<n;i++)if(du[i]==n-1)return i;
        return -1;
    }
    vector<int>a,b,t,t1;
    for(int i=0;i<n;i++)t.push_back(i);int nn=n;
    for(int nm=1;nm<=8;nm++){
        int num=Nm[nm];
        t1=t;
        for(int i=0;i<nn;i++)du[i]=0;
        n=t.size();a.clear(),b.clear();
        int s=ceil(1.0*n/num);R[0]=-1;
        for(int i=1;i<=num;i++){
            L[i]=R[i-1]+1;
            if(n%num==0)R[i]=L[i]+s-1;
            else if(n%num>=i)R[i]=L[i]+s-1;else R[i]=L[i]+s-2;
            for(int j=L[i];j<=R[i];j++)for(int k=j+1;k<=R[i];k++)a.push_back(t[j]),b.push_back(t[k]);
            
        }
        t=ask(a,b);
        for(int x:t)du[x]++;
        a.clear(),b.clear();t.clear();
        for(int i=1;i<=num;i++){
            int len=R[i]-L[i];
            for(int j=L[i];j<=R[i];j++)if(du[t1[j]]==len)t.push_back(t1[j]);
        }
    }
    return t[0];
}