//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 dv[12][N],lef[N],rig[N];bool wk[1003][1003];
map< pair<int,int>,int >mp[N];vector< pair<int,int> >ranges[25];
// inline vector<int> ask(vector<int>A,vector<int>B){
//     int sz=A.size();vector<int>C;
//     rep(i,0,sz-1){
//         cout<<"? "<<A[i]<<' '<<B[i]<<endl;
//         int R;cin>>R,C.push_back(R);
//     }
//     return C;
// }
inline void prework(int dep,int l,int r){
    ranges[dep].push_back({l,r});
    // if (l>r) cout<<dep<<' '<<l<<','<<r<<" ???\n";
    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;
    }
}
// inline int work(int dep,int l,int r){
//     if (dv[dep][r-l+1]==-1){
//         if (l==r) return l;
//         int Max=l;
//         vector<int>A,B;
//         int len=r-l+1;
//         rep(i,0,len) rep(j,0,len) wk[i][j]=0;
//         rep(i,l,r) rep(j,i+1,r)
//             A.push_back(i),B.push_back(j);
//         vector<int>C=ask(A,B);
//         int sz=C.size();
//         rep(i,0,sz-1)
//             if (C[i]==1) wk[B[i]-l][A[i]-l]=1,wk[A[i]-l][B[i]-l]=0;
//             else wk[B[i]-l][A[i]-l]=0,wk[A[i]-l][B[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;}
//         }
//         return Max;
//     }
//     int len=r-l+1,K=dv[dep][len];
//     int A=len/K,B=len/K+1;
//     int cntB=len-A*K,cntA=(len-B*cntB)/A,gr=cntA+cntB;
//     vector<int>Id,aa,bb,cc,dd;r=l;
//     rep(i,1,gr){
//         if (cntB) r=B+l-1,--cntB;
//         else r=A+l-1,--cntA;
//         Id.push_back(work(dep-1,l,r));
//         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)
//         aa.push_back(Id[i]),bb.push_back(Id[j]),
//         cc.push_back(i),dd.push_back(j);
//     vector<int>C=ask(aa,bb);
//     rep(i,0,(int)C.size()-1){
//         int A=cc[i],B=dd[i];
//         if (C[i]==1) 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;}
//     }
//     return Max;
// }
int richest(int n,int t,int s){
    memset(dp,0x3f,sizeof(dp));
    int mx=9;
    rep(i,0,mx) mp[i].clear(),ranges[i].clear();
    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(20,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;
        }
    }
    prework(mx,0,n-1);
    // return 0;
    // cerr<<"Over?\n";
    rep(Dep,1,mx){
        vector<int>askA,askB;
        // cerr<<Dep<<" yiw?\n";
        for (auto R:ranges[Dep]){
            int dep=Dep,l=R.first,r=R.second;
            if (l==r){mp[dep][{l,r}]=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;
                    // cout<<dep-1<<' '<<l<<','<<r<<" ???\n";
                    Id.push_back(mp[dep-1][{l,r}]);
                    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;
        // cerr<<askA.size()<<" ohhh\n";
        // cout<<Dep<<" :\n";
        // for (auto i:askA) cout<<i<<' ';cout<<'\n';
        // for (auto i:askB) cout<<i<<' ';cout<<'\n';
        vector<int>ResultC=ask(askA,askB);
        for (auto R:ranges[Dep]){
            int dep=Dep,l=R.first,r=R.second;
            if (l==r) continue;
            // cout<<dep<<' '<<l<<','<<r<<" ?ASD?SD?\n";
            if (dv[dep][r-l+1]==-1){
                int Max=-1,len=r-l+1;
                // if (len>100) cerr<<"Lose\n";
                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,r}]=Max;
            }else{
                // cerr<<"in>?\n";
                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,r}]);
                    l=r+1;
                }
                int Sz=Id.size(),Max=-1;
                // cerr<<Sz<<" md?\n";
                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);
                // cerr<<lef[ll]<<','<<rig[ll]<<' '<<cc.size()<<','<<dd.size()<<" ohhh\n";
                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;
                }
                // cerr<<"NextOver?\n";
                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;}
                }
                // cout<<Max<<" yiw?\n";
                mp[dep][{ll,rr}]=Max;
                // cerr<<"out?\n";
            }
        }
    }
    return mp[mx][{0,n-1}];
    // return work(mx,0,n-1);
}
// signed main(){
//     int n;cin>>n;
//     return cout<<richest(n,9,10)<<" !\n",0;
// }