#include "richest.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// vector<int> ask(vector<int> i, vector<int> j) {
//     assert((int)i.size() == (int)j.size());
//     vector<int> ret;
//     for (int idx = 0; idx < (int)i.size(); idx++) {
//         cout << "? " << i[idx] << ' ' << j[idx] << endl;
//         int res;
//         cin >> res;
//         ret.push_back(res);
//     }
//     return ret;
// }
vector<int> getmx(int sz, 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(sz, 0);
    int cur = 0, cursz = 0;
    for (auto svec : vec) {
        for (int i = 0; i < (int)svec.size(); i++) {
            for (int j = i + 1; j < (int)svec.size(); j++) {
                if (res[cur] == svec[i]) {
                    cnt[cursz + i]++;
                } else {
                    cnt[cursz + j]++;
                }
                cur++;
            }
        }
        cursz += (int)svec.size();
    }
    vector<int> ret;
    cursz = 0;
    for (auto svec : vec) {
        for (int i = 0; i < (int)svec.size(); i++) {
            if (cnt[cursz + i] == (int)svec.size() - 1) {
                ret.push_back(svec[i]);
            }
        }
        cursz += (int)svec.size();
    }
    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((int)cur.size(), qs);
    }
    return cur[0];
}
// int main() {
//     int N, T, S;
//     cin >> N >> T >> S;
//     cout << richest(N, T, S) << '\n';
//     return 0;
// }