#include "richest.h"
#include <bits/stdc++.h>
#define INF 1000000009
using namespace std;
typedef long long ll;

int num[200]={ 5536, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 
5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 
5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 
5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 
5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 
5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 
5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 
5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 
5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 
5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 
5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 5472, 
5472, 5472, 5472, 5472, 5472, 5184, 5184, 5184, 5184, 5184 };

const int mx=183;

int num5536[20]={ 352, 288, 288, 288, 288, 288, 288, 288, 288, 288, 288, 288, 
                288, 288, 288, 288, 288, 288, 288 };
const int mx5536=19;

int num5472[20]={ 288, 288, 288, 288, 288, 288, 288, 288, 288, 288, 288, 288, 
                288, 288, 288, 288, 288, 288, 288 };
const int mx5472=19;

int num5184[20]={ 288, 288, 288, 288, 288, 288, 288, 288, 288, 288, 288, 288, 
                288, 288, 288, 288, 288, 288 };
const int mx5184=18;

int f[500][500], rec[500][500], pfa[1000008];
vector <int> vec[10][500];
vector <int> curA, curB, curC;
vector <int> qry[1000008], que[10];

struct Pnt { int l, r; } rng[1000008];
int tot;
bool tg[1000006];

void precal ()
{
    int n=400, K=6;
    for (int i=1; i<=n; i++) {
        for (int j=0; j<=n; j++) { f[i][j]=INF; }
    }
    f[1][1]=0;
    for (int k=0; k<=K; k++) {
        for (int i=2; i<=n; i++) {
            if (k>0) {
                for (int j=2; j<=i; j++) {
                    f[i][1]=min(f[i][1], f[i][j]);
                    if (f[i][1]==f[i][j]) rec[i][1]=j;
                }
            }
        }

        for (int i=1; i<=n; i++) {
            int ii=i, jj=rec[i][1];
            if (vec[k][i].size()>0) { return; }
            while (jj>1) {
                int cur=rec[ii][jj];
                vec[k][i].push_back(cur);
                jj=jj-1; ii=ii-cur;
            }
            vec[k][i].push_back(ii);
        }

        for (int i=2; i<=n; i++) {
            for (int j=i; j>=2; j--) {
                for (int cur=1; cur<=i-j+1; cur++) {
                    f[i][j]=min(f[i][j], f[i-cur][j-1]+f[cur][1]+(j-1));
                    if (f[i][j]==f[i-cur][j-1]+f[cur][1]+(j-1)) rec[i][j]=cur;
                }
            }
        }
    }
}

void cal (int l, int r, int lv, int fa)
{
    if (l==r) { qry[fa].push_back(l); return; }

    int u=++tot; rng[u]=(Pnt){ l, r };
    que[lv].push_back(u);
    pfa[u]=fa;

    int pre=l;
    if (lv==8) {
        for (int i=0; i<mx; i++) { cal(pre, pre+num[i]-1, lv-1, u); pre+=num[i]; }
    }
    else if (lv==7) {
        if (r-l+1==5536) {
            for (int i=0; i<mx5536; i++) { cal(pre, pre+num5536[i]-1, lv-1, u); pre+=num5536[i]; }
        }
        else if (r-l+1==5472) {
            for (int i=0; i<mx5472; i++) { cal(pre, pre+num5472[i]-1, lv-1, u); pre+=num5472[i]; }
        }
        else if (r-l+1==5184) {
            for (int i=0; i<mx5184; i++) { cal(pre, pre+num5184[i]-1, lv-1, u); pre+=num5184[i]; }
        }
    }
    else {
        for (int i=0; i<(int)vec[lv][r-l+1].size(); i++) {
            cal(pre, pre+vec[lv][r-l+1][i]-1, lv-1, u);
            pre+=vec[lv][r-l+1][i];
        }
    }
}

void ins (int u)
{
    for (int i=0; i<(int)qry[u].size(); i++) {
        for (int j=0; j<i; j++) {
            curA.push_back(qry[u][i]);
            curB.push_back(qry[u][j]);
        }
    }
}
void query ()
{
    curC=ask(curA, curB);
    for (int i=0; i<(int)curC.size(); i++) {
        if (curC[i]!=curA[i]) { tg[curA[i]]=0; }
        if (curC[i]!=curB[i]) { tg[curB[i]]=0; }
    }
}

int richest(int N, int T, int S)
{
    if (N==1000000) {
        precal();
        for (int i=0; i<=tot; i++) { qry[i].clear(); } tot=0;
        for (int i=0; i<=8; i++) { que[i].clear(); }

        cal(0, N-1, 8, 0);

        fill(tg, tg+N, 1);
        for (int lv=1; lv<=8; lv++) {
            curA.clear(); curB.clear(); curC.clear();

            for (int i=0; i<(int)que[lv].size(); i++) {
                int u=que[lv][i]; ins(u);
            }
            query();
            int cnt=0;
            for (int i=0; i<(int)que[lv].size(); i++) {
                int u=que[lv][i];
                for (int j=rng[u].l; j<=rng[u].r; j++) {
                    if (tg[j]) { qry[pfa[u]].push_back(j); break; }
                }
            }
        }

        return qry[0][0];
    }
    else {
        curA.clear(); curB.clear(); curC.clear();
        fill(tg, tg+N, 1);

        for (int i=0; i<N; i++) {
            for (int j=0; j<i; j++) {
                curA.push_back(i);
                curB.push_back(j);
            }
        }
        query();
        for (int i=0; i<N; i++) if (tg[i]) { return i; }
    }
}