#include"richest.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
int const N=1e6+10;
int dp[9][N],pre[9][N];bool nt[N];
inline int get(int x,int y){
    if (y==1) return 0;
    if (x==1) return y*(y-1)/2;
    if (~dp[x][y]) return dp[x][y];
    int res=2e9,Pre=0,lim=min(20ll,(int)sqrt(y));
    rep(i,1,lim){
        int ans=get(x-1,(y+i-1)/i),A=y/i,B=y%i;
        ans+=A*(i*(i-1)/2)+B*(B-1)/2;
        if (res>ans) Pre=-i,res=ans;
    }
    rep(I,1,lim) rep(i,max(1ll,y/I-2),min(y,y/I+2)){
        int ans=get(x-1,i),A=y/i,B=y%i;
        ans+=(i-B)*(A*(A-1)/2)+B*(A*(A+1)/2);
        if (res>ans) Pre=i,res=ans;
    }
    return pre[x][y]=Pre,dp[x][y]=res;
}
#undef int
int richest(int N,int T,int S){
    memset(dp,-1,sizeof(dp)),T=min(T,8);
    if (N<=1000) T=1;
    int R=get(T,N);
    vector<int>res;
    rep(i,0,N-1) res.push_back(i);
    per(i,T,1){
        int A=pre[i][N];
        memset(nt,0,sizeof(nt));
        if (i==1){
            vector<int>a,b;
            rep(i,1,N) rep(j,i+1,N)
                a.push_back(res[i-1]),b.push_back(res[j-1]);
            vector<int>c=ask(a,b);
            int sz=-1;
            rep(i,1,N) rep(j,i+1,N){
                ++sz;
                if (c[sz]==a[sz]) nt[j]=1;
                else nt[i]=1;
            }
            rep(i,1,N) if (!nt[i])
                return res[i-1];
        }
        if (A<0){
            A=-A;
            int a=N/A,b=N%A,id=-1,qr=-1;
            vector<int>Q,aa,bb,g;
            rep(I,1,a){
                vector<int>c;
                rep(j,1,A) ++id,c.push_back(res[id]);
                rep(j,0,A-1) rep(k,j+1,A-1)
                    aa.push_back(c[j]),bb.push_back(c[k]);
            }
            {
                vector<int>c;
                rep(j,1,b) ++id,c.push_back(res[id]);
                rep(j,0,b-1) rep(k,j+1,b-1)
                    aa.push_back(c[j]),bb.push_back(c[k]);
            }
            Q=ask(aa,bb),id=-1;
            rep(I,1,a){
                vector<int>c;
                rep(j,1,A) ++id,c.push_back(res[id]);
                rep(j,0,A-1) rep(k,j+1,A-1){
                    ++qr;
                    if (Q[qr]==c[j]) nt[c[k]]=1;
                    else nt[c[j]]=1;
                }
                rep(j,0,A-1) if (!nt[c[j]]) g.push_back(c[j]);
            }
            {
                vector<int>c;
                rep(j,1,b) ++id,c.push_back(res[id]);
                rep(j,0,b-1) rep(k,j+1,b-1){
                    ++qr;
                    if (Q[qr]==c[j]) nt[c[k]]=1;
                    else nt[c[j]]=1;
                }
                rep(j,0,b-1) if (!nt[c[j]]) g.push_back(c[j]);
            }
            N=(N+A-1)/A,res=g;
        }else{
            vector<int>Q,aa,bb,g;
            int a=N/A,b=N%A,id=-1;
            rep(i,1,b){
                //a+1
                vector<int>c;
                rep(j,1,a+1) ++id,c.push_back(res[id]);
                rep(j,0,a) rep(k,j+1,a)
                    aa.push_back(c[j]),bb.push_back(c[k]);
            }
            rep(i,1,A-b){
                //a
                vector<int>c;
                rep(j,1,a) ++id,c.push_back(res[id]);
                rep(j,0,a-1) rep(k,j+1,a-1)
                    aa.push_back(c[j]),bb.push_back(c[k]);
            }
            Q=ask(aa,bb),id=-1;
            int sz=-1;
            rep(i,1,b){
                //a+1
                vector<int>c;
                rep(j,1,a+1) ++id,c.push_back(res[id]);
                rep(j,0,a) rep(k,j+1,a){
                    ++sz;
                    if (c[j]==Q[sz]) nt[c[k]]=1;
                    else nt[c[j]]=1;
                }
                rep(j,0,a) if (!nt[c[j]]) g.push_back(c[j]);
            }
            rep(i,1,A-b){
                //a
                vector<int>c;
                rep(j,1,a) ++id,c.push_back(res[id]);
                rep(j,0,a-1) rep(k,j+1,a-1){
                    ++sz;
                    if (c[j]==Q[sz]) nt[c[k]]=1;
                    else nt[c[j]]=1;
                }
                rep(j,0,a-1) if (!nt[c[j]]) g.push_back(c[j]);
            }
            N=A,res=g;
        }
    }
    return res[0];
}