#include "richest.h"
#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;
const int maxn = 1000000;

vi qa, qb, qc;
int deg[maxn + 5];
int op[9] = {1000000, 500000, 250000, 125000, 62498, 20832, 3472, 183, 1};

vi reduce(vi &rem, int y)
{
    qa.clear(), qb.clear(); vi res; res.clear();
    int x = rem.size(), b = x % y, a = y - b, z = x / y, pos = 0;
    for (int i = 0; i < a; i++)
    {
        for (int j = 0; j < z; j++)
            for (int k = j + 1; k < z; k++)
                qa.emplace_back(rem[pos + j]), qb.emplace_back(rem[pos + k]);
        pos += z;
    }
    for (int i = 0; i < b; i++)
    {
        for (int j = 0; j <= z; j++)
            for (int k = j + 1; k <= z; k++)
                qa.emplace_back(rem[pos + j]), qb.emplace_back(rem[pos + k]);
        pos += (z + 1);
    }
    qc = ask(qa, qb); int nowk = 0; pos = 0;
    for (int i = 0; i < maxn; i++) deg[i] = 0;
    for (int i = 0; i < a; i++)
    {
        for (int j = 0; j < z; j++)
            for (int k = j + 1; k < z; k++)
                deg[qc[nowk]]++, nowk++;
        for (int j = 0; j < z; j++) if (deg[rem[pos + j]] == z - 1) res.emplace_back(rem[pos + j]);
        pos += z;
    }
    for (int i = 0; i < b; i++)
    {
        for (int j = 0; j <= z; j++)
            for (int k = j + 1; k <= z; k++)
                deg[qc[nowk]]++, nowk++;
        for (int j = 0; j <= z; j++) if (deg[rem[pos + j]] == z) res.emplace_back(rem[pos + j]);
        pos += (z + 1);
    }
    return res;
}

int richest(int N, int T, int S)
{
    vi rem; rem.clear();
    for (int i = 0; i < N; i++) rem.emplace_back(i);
    if (T == 1)
    {
        rem = reduce(rem, 1);
        return rem[0];
    }

    for (int i = 1; i <= 8; i++) rem = reduce(rem, op[i]);
    return rem[0];
}