#include <bits/stdc++.h>
#include "richest.h"
using namespace std;
const int N=1e6+10;
int du[N];
int L[200],R[200];
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);
    for(int c=1;c<=8;c++){
        int sz=t.size(),tmp=-1;
        if(sz&1)tmp=t[sz/2];
        a.clear(),b.clear();
        for(int i=0;i<sz/2;i++)a.push_back(t[i]),b.push_back(t[sz-i-1]);
        t=ask(a,b);
        
        if(tmp!=-1)t.push_back(tmp);
    }
    t1=t;int nn=n;
    for(int i=0;i<nn;i++)du[i]=0;
    n=t.size();a.clear(),b.clear();
    int s=ceil(1.0*n/128);R[0]=-1;
    for(int i=1;i<=128;i++){
        L[i]=R[i-1]+1,R[i]=min(n-1,L[i]+s-1);
        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<=128;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]);
    }
    for(int i=0;i<nn;i++)du[i]=0;
    n=t.size();
    for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)a.push_back(t[i]),b.push_back(t[j]);
    t=ask(a,b);
    for(int x:t)du[x]++;
    for(int x:t)if(du[x]==n-1)return x;
    return -1;
}