#include "richest.h"
#include<bits/stdc++.h>
#define pii pair<int,int>
#define mp make_pair
#define ll long long
using namespace std;

namespace sub1{
    const int maxn=1010;
    int n=1000;
    vector<int>A,B;
    int is[maxn][maxn];
    int solve(int N){
        n=N;
        A.clear();B.clear();
        for(int i=0;i<n;i++)
            for(int j=i+1;j<n;j++){
                A.push_back(i);
                B.push_back(j);
                // cerr<<i<<' '<<j<<"|"<<n<<endl;
            }
        auto C=ask(A,B);int cnt=0;
        for(int i=0;i<n;i++)
            for(int j=i+1;j<n;j++){
                is[i][j]=(C[cnt++]==i);
                is[j][i]=1-is[i][j];
            }
        for(int i=0;i<n;i++){
            bool flg=true;
            for(int j=0;j<n;j++)
                if(i!=j && !is[i][j])flg=false;
            if(flg)return i;
        }
        assert(0);
    }
}

namespace sub2{
    const int maxn=1000010,maxt=21;
    const int maxm=510;
    int n,s,t;
    int dp[maxn][maxt];
    // int to[maxn][maxt];
    bool is[maxn][maxt];
    int dp2[maxm][maxt][maxm];
    pii to[maxn][maxt];
    const int tMax[25]={0,0,20,6,3,2,1,1,1};
    int dfs(int N,int T){
        if(is[N][T])return dp[N][T];
        to[N][T]=mp(N,1);
        if(N==1)return 0;
        if(T==1)return (int)min(1000000000ll,1ll*N*(N-1)/2);
        else{
            // if(rand()%3000==0)cerr<<"dfs "<<N<<' '<<T<<' '<<is[N][T]<<endl;
            int ans=1e9,chs=0,si=-1;
            for(int i=1;i<=tMax[T];i++){
                // use i+1 / i
                int t=N/i;
                int lst=N-t*i;
                int numI1=lst,numI=t-lst;
                if(numI<0)continue;
                if(i==1)numI1=N/2,numI=N&1;
                int cntI1=(i*(i-1)/2),cntI=(i+1)*i/2;
                int Gap=max(1,(numI)/(i+1)/500);
                for(;numI>=0;numI1+=i*Gap,numI-=(i+1)*Gap){
                    int tans=dfs(numI+numI1,T-1)+numI*cntI1+numI1*cntI;
                    if(tans<ans){
                        ans=tans;
                        chs=i;
                        si=numI;
                        // if(T==8)cerr<<"si="<<si<<endl;
                    }
                }
            }
            is[N][T]=1;to[N][T]=mp(chs,si);
            return dp[N][T]=ans;
        }
    }
    bool ok[maxn];
    int solve(int N,int S,int T){
        memset(ok,0,sizeof(ok));
        T=8;dfs(N,T);
        // cerr<<' '<<dp[N][T]<<endl;
        // return 1;
        n=N;s=S;t=T;
        vector<int>now;
        for(int i=0;i<n;i++)now.push_back(i);
        int tnow=T;
        while(now.size()!=1){
            int ntmp=now.size();
            int y=to[ntmp][tnow].first;
            // cerr<<"   "<<ntmp<<' '<<y<<' '<<tnow<<"|"<<to[ntmp][tnow].second<<endl;
            int t=ntmp/y;
            int numI=to[ntmp][tnow].second,numI1=(now.size()-y*numI)/(y+1);
            // if(y==1)numI1=ntmp/2,numI=ntmp&1;
            tnow--;
            int cnt=0;
            vector<int>q1,q2;
            // cerr<<"now.size()="<<now.size()<<" | "<<y<<' '<<tnow<<" | "<<numI<<' '<<numI1<<endl;
            for(int i=1;i<=numI;i++){
                vector<int>u;
                for(int j=1;j<=y;j++)
                    u.push_back(now[cnt+j-1]);
                cnt+=y;
                for(int j=0;j<y;j++)
                    for(int k=j+1;k<y;k++){
                        q1.push_back(u[j]);
                        q2.push_back(u[k]);
                    }
            }
            for(int i=1;i<=numI1;i++){
                vector<int>u;
                for(int j=1;j<=y+1;j++)
                    u.push_back(now[cnt+j-1]);
                cnt+=y+1;
                for(int j=0;j<y+1;j++)
                    for(int k=j+1;k<y+1;k++){
                        q1.push_back(u[j]);
                        q2.push_back(u[k]);
                    }
            }
            // cerr<<q1.size()<<endl;
            vector<int> ret=ask(q1,q2);
            for(int i=0;i<ret.size();i++)
                ok[q1[i]+q2[i]-ret[i]]=1;
            now.clear();
            for(int i=0;i<n;i++)
                if(!ok[i])now.push_back(i);
            // cerr<<now.size()<<endl;
        }
        return now[0];
    }
}

int richest(int N, int T, int S) {
    if(N<=1000)return sub1::solve(N);
    return sub2::solve(N,S,T);
}