#include "richest.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> getmx(int N, vector<vector<int>> vec) {
    vector<int> q1, q2;
    for (auto svec : vec) {
        for (int i = 0; i < (int)svec.size(); i++) {
            for (int j = i + 1; j < (int)svec.size(); j++) {
                q1.push_back(svec[i]);
                q2.push_back(svec[j]);
            }
        }
    }
    vector<int> res = ask(q1, q2);
    vector<int> cnt(N, 0);
    int cur = 0;
    for (auto svec : vec) {
        for (int i = 0; i < (int)svec.size(); i++) {
            for (int j = i + 1; j < (int)svec.size(); j++) {
                cnt[res[cur]]++;
                cur++;
            }
        }
    }
    vector<int> ret;
    for (auto svec : vec) {
        for (int i = 0; i < (int)svec.size(); i++) {
            if (cnt[svec[i]] == (int)svec.size() - 1) {
                ret.push_back(svec[i]);
            }
        }
    }
    return ret;
}
int richest(int N, int T, int S) {
    if (T == 1) {
        vector<int> vec;
        for (int i = 0; i < N; i++) {
            vec.push_back(i);
        }
        vector<vector<int>> tmp;
        tmp.push_back(vec);
        return getmx(N, tmp)[0];
    }
    vector<int> cur, nxt;
    for (int i = 0; i < N; i++) {
        cur.push_back(i);
    }
    const int t = 8;
    const int table[t] = {500000, 250000, 125000, 62500, 20833, 3472, 183, 1};
    for (int i = 0; i < t; i++) {
        int st = 0;
        vector<vector<int>> qs;
        for (int j = 0; j < table[i]; j++) {
            vector<int> q;
            int sz = (int)cur.size() / table[i] + (j < (int)cur.size() % table[i]);
            for (int ii = 0; ii < sz; ii++) {
                q.push_back(cur[st + ii]);
            }
            qs.push_back(q);
            st += sz;
        }
        cur = getmx(N, qs);
    }
    return cur[0];
}