//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;/*
int w[N],ct=0,cs=0;
mt19937 rnd(time(0));
vector<int> ask(vector<int> a,vector<int> b)
{
    int sz=a.size();ct++;cs+=sz;
    vector<int> c;
    for(int i=0;i<sz;i++)
    {
        if(w[a[i]]>w[b[i]])c.push_back(a[i]);
        else c.push_back(b[i]);
    }return c;
}*/
#include "richest.h"
using ll=long long;
const ll inf=1e18+7;
int gt(vector<int> vc)
{
    int sz=vc.size();
    static bool vis[1000005];
    for(int i=0;i<sz;i++)vis[i]=0;
    vector<int> a,b;int ct=0;
    for(int i=0;i<sz;i++)for(int j=i+1;j<sz;j++)
    a.push_back(vc[i]),b.push_back(vc[j]);
    vector<int> c=ask(a,b);
    for(int i=0;i<sz;i++)for(int j=i+1;j<sz;j++)
    {if(c[ct]==vc[i])vis[j]=1;else vis[i]=1;ct++;}
    for(int i=0;i<sz;i++)if(!vis[i])return vc[i];
}
int slv1(int n)
{
    vector<int> vc;
    for(int i=1;i<=n;i++)vc.push_back(i-1);
    return gt(vc);
}bool cked=0;
//slv1 up | slv2 down
vector<int> gp[65][65];
vector<int> fr[6][65];
ll f[6][65],g[65][65];
vector<int> typ[9];
vector<int> dg[1000005];
int a[4][6]={
{47,47,48,48,48,48},
{47,48,48,48,48,48},
{48,48,48,48,56,56},
{48,48,48,53,54,54},
};
int b[4]={286,287,304,305};
vector<int> sn[N],gr[N];int tot=0;
int tl[N],tr[N],d[N],vl[N],ql[N],qr[N];
bool vis[N];
int solve(int L,int R,int t)
{
    int cr=++tot;
    tl[cr]=L,tr[cr]=R,d[cr]=t;
    if(t==1)return cr;
    if(t>=6)
    {
        vector<int> vc;
        int len=R-L+1,l=L,r;
        for(auto c:dg[len])
        {
            r=l+c-1;
            sn[cr].push_back(solve(l,r,t-1));
            l=r+1;
        }assert(l==R+1);
    }
    else
    {
        vector<int> vc;
        int len=R-L+1,l=L,r;
        assert(len<=60);
        for(auto c:fr[t][len])
        {
            r=l+c-1;
            sn[cr].push_back(solve(l,r,t-1));
            l=r+1;
        }assert(l==R+1);
    }
    return cr;
}
void init()
{
    int m=60;
    for(int i=1;i<=m;i++)f[1][i]=1ll*i*(i-1)/2;
    for(int i=1;i<=m;i++)fr[1][i].push_back(1);
    for(int t=2;t<=5;t++)
    {
        for(int i=0;i<=m;i++)for(int j=0;j<=m;j++)
        g[i][j]=inf;g[0][0]=0;gp[0][0].clear();
        for(int i=1;i<=m;i++)
        {
            for(int j=i;j<=m;j++)for(int k=1;k<=m;k++)
            {
                ll val=g[j-i][k-1]+f[t-1][i];
                if(g[j][k]>val)
                {
                    gp[j][k]=gp[j-i][k-1];
                    gp[j][k].push_back(i);
                    g[j][k]=val;
                }
            }
        }
        for(int i=1;i<=m;i++)
        {
            f[t][i]=inf;
            for(int j=1;j<=m;j++)
            {
                if(f[t][i]>f[1][j]+g[i][j])
                {
                    f[t][i]=f[1][j]+g[i][j];
                    fr[t][i]=gp[i][j];
                }
            }
        }
    }
    int v=1e6;
    for(int i=1;i<=195;i++)
    dg[v].push_back(4878);
    for(int i=1;i<=10;i++)
    dg[v].push_back(4879);
    dg[4878].push_back(286);
    for(int i=1;i<=16;i++)
    dg[4878].push_back(287);
    dg[4879].push_back(304);
    for(int i=1;i<=15;i++)
    dg[4879].push_back(305);
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<6;j++)
        dg[b[i]].push_back(a[i][j]);
    }solve(1,1000000,8);
    for(int i=1;i<=tot;i++)
    typ[d[i]].push_back(i);
    //cout<<tot<<'\n';
}
int slv2()
{
    if(!cked)init(),cked=1;
    vector<int> va,vb,c;
    for(auto i:typ[1])
    {
        for(int j=tl[i];j<=tr[i];j++)
        for(int k=j+1;k<=tr[i];k++)
        va.push_back(j-1),vb.push_back(k-1);
    }c=ask(va,vb);int ct=0;
    for(auto i:typ[1])
    {
        for(int j=tl[i];j<=tr[i];j++)vis[j]=0;
        for(int j=tl[i];j<=tr[i];j++)
        for(int k=j+1;k<=tr[i];k++)
        {
            if(c[ct]==j-1)vis[k-1]=1;
            else vis[j-1]=1;ct++;
        }
        for(int j=tl[i];j<=tr[i];j++)
        if(!vis[j-1])vl[i]=j-1;
    }
    for(int x=2;x<=8;x++)
    {
        va.clear(),vb.clear();
        for(auto i:typ[x])
        {
            vector<int> vc;int sz=sn[i].size();
            for(auto v:sn[i])vc.push_back(vl[v]);
            for(int j=0;j<sz;j++)for(int k=j+1;k<sz;k++)
            va.push_back(vc[j]),vb.push_back(vc[k]);
        }c=ask(va,vb);ct=0;
        for(auto i:typ[x])
        {
            vector<int> vc;int sz=sn[i].size();//cout<<sz<<' ';
            for(auto v:sn[i])vc.push_back(vl[v]);
            for(int j=0;j<sz;j++)vis[j]=0;
            for(int j=0;j<sz;j++)
            for(int k=j+1;k<sz;k++)
            {
                if(c[ct]==vc[j])vis[k]=1;
                else vis[j]=1;ct++;
            }
            for(int j=0;j<sz;j++)
            if(!vis[j])vl[i]=vc[j];
            int ps=0;
        }//cout<<'\n';
    }return vl[1];
}
int richest(int n,int t,int s)
{
    if(t==1)return slv1(n);
    else return slv2();
}/*
void work()
{
    for(int T=1;T<=10;T++)
    {
        for(int i=1;i<=1000000;i++)w[i]=i;
        for(int i=1;i<=1000000;i++)
        {
            int x=rnd()%1000000+1,y=rnd()%1000000+1;
            swap(w[x],w[y]);
        }ct=0,cs=0;cout<<"# "<<T<<" : ";
        if(w[richest(1000000,8,2000000)]==1000000)
        {
            cout<<ct<<' '<<cs<<' '<<"AC qwq\n";
        }
        else
        {
            cout<<ct<<' '<<cs<<' '<<"WA!!!\n";
        }
    }
}
int main()
{
    work();
    return 0;
}*/