//A tree without skin will surely die.
//A man without face will be alive.
#include<bits/stdc++.h>
#include "richest.h"
using namespace std;
#define rep(i,j,k) for(int i=j;i<=k;++i)
int const N=1e6+10;
long long dp[12][N];int mp[12][N],dv[12][N],lef[N],rig[N];bool wk[1003][1003];
vector< pair<int,int> >ranges[12];
inline void prework(int dep,int l,int r){
    ranges[dep].push_back({l,r});
    if (dv[dep][r-l+1]==-1) return;
    int len=r-l+1,K=dv[dep][len],A=len/K,B=len/K+1,cntB=len-A*K,cntA=(len-B*cntB)/A,gr=cntA+cntB;
    rep(i,1,gr){
        if (cntB) r=B+l-1,--cntB;
        else r=A+l-1,--cntA;
        prework(dep-1,l,r),l=r+1;
    }
}
int richest(int n,int t,int s){
    int mx=min(9,t);
    rep(i,0,mx) ranges[i].clear();
    if (n==1000){
        rep(i,1,mx) rep(j,1,n){
            dp[i][j]=1ll*j*(j-1)/2,dv[i][j]=-1;
            if (i==1) continue;
            rep(divide,1,min(15,j)){
                int A=j/divide,B=j/divide+1;
                int cntB=j-A*divide,cntA=(j-B*cntB)/A;
                long long val=dp[i-1][A]*cntA+dp[i-1][B]*cntB+(divide-1)*divide/2;
                dp[i][j]=min(dp[i][j],val);
                if (val==dp[i][j]) dv[i][j]=divide;
            }
        }
    }else{
        dv[9][1000000]=15;
        dv[8][66667]=15;
        dv[7][4445]=14;
        dv[6][318]=5;
        dv[5][64]=4;
        dv[4][16]=2;
        dv[3][8]=2;
        dv[2][4]=2;
        dv[1][2]=-1;
        dv[5][63]=4;
        dv[4][15]=2;
        dv[3][7]=2;
        dv[2][3]=2;
        dv[1][1]=-1;
        dv[6][317]=5;
        dv[7][4444]=14;
        dv[8][66666]=15;
    }
    prework(mx,0,n-1);
    rep(Dep,1,mx){
        vector<int>askA,askB;
        for (auto R:ranges[Dep]){
            int dep=Dep,l=R.first,r=R.second;
            if (l==r){mp[dep][l]=l;continue;}
            if (dv[dep][r-l+1]==-1){
                lef[l]=askA.size();
                rep(i,l,r) rep(j,i+1,r)
                    askA.push_back(i),askB.push_back(j);
                rig[l]=askA.size()-1;
            }else{
                int ll=l,len=r-l+1,K=dv[dep][len],A=len/K,B=len/K+1,cntB=len-A*K,cntA=(len-B*cntB)/A,gr=cntA+cntB;
                vector<int>Id;r=l;rep(i,1,gr){
                    if (cntB) r=B+l-1,--cntB;
                    else r=A+l-1,--cntA;
                    Id.push_back(mp[dep-1][l]);
                    l=r+1;
                }
                int Sz=Id.size();
                lef[ll]=askA.size();
                rep(i,0,Sz-1) rep(j,i+1,Sz-1)
                    askA.push_back(Id[i]),askB.push_back(Id[j]);
                rig[ll]=askA.size()-1;
            }
        }
        if (!askA.size()) continue;
        vector<int>ResultC=ask(askA,askB);
        for (auto R:ranges[Dep]){
            int dep=Dep,l=R.first,r=R.second;
            if (l==r) continue;
            if (dv[dep][r-l+1]==-1){
                int Max=-1,len=r-l+1;
                rep(i,0,len) rep(j,0,len) wk[i][j]=0;
                int sz=ResultC.size();
                rep(i,lef[l],rig[l])
                    if (ResultC[i]==askB[i]) wk[askB[i]-l][askA[i]-l]=1,wk[askA[i]-l][askB[i]-l]=0;
                    else wk[askB[i]-l][askA[i]-l]=0,wk[askA[i]-l][askB[i]-l]=1;
                rep(i,l,r){
                    int tag=1;
                    rep(j,l,r) if (i!=j) tag&=wk[i-l][j-l];
                    if (tag){Max=i;break;}
                }
                mp[dep][l]=Max;
            }else{
                int ll=l,rr=r,len=r-l+1,K=dv[dep][len],A=len/K,B=len/K+1,cntB=len-A*K,cntA=(len-B*cntB)/A,gr=cntA+cntB;
                vector<int>Id,cc,dd;r=l;
                rep(i,1,gr){
                    if (cntB) r=B+l-1,--cntB;
                    else r=A+l-1,--cntA;
                    Id.push_back(mp[dep-1][l]);
                    l=r+1;
                }
                int Sz=Id.size(),Max=-1;
                rep(i,0,Sz) rep(j,0,Sz) wk[i][j]=0;
                rep(i,0,Sz-1) rep(j,i+1,Sz-1)
                    cc.push_back(i),dd.push_back(j);
                rep(i,lef[ll],rig[ll]){
                    int A=cc[i-lef[ll]],B=dd[i-lef[ll]];
                    if (ResultC[i]==Id[B]) wk[B][A]=1,wk[A][B]=0;
                    else wk[B][A]=0,wk[A][B]=1;
                }
                rep(i,0,Sz-1){
                    int tag=1;
                    rep(j,0,Sz-1) if (i!=j) tag&=wk[i][j];
                    if (tag){Max=Id[i];break;}
                }
                mp[dep][ll]=Max;
            }
        }
    }
    return mp[mx][0];
}