#include "richest.h"

#include <bits/stdc++.h>
using namespace std;

const int levels[] = {1000000, 500000, 250000, 125000, 62496,
                      20832,   3472,   183,    1};

const int MAX_N = 1'000'005;
int _del_date[MAX_N];
int _cur_date = 1;

vector<int> query(vector<vector<int>> groups) {
    _cur_date++;
    vector<int> side_a, side_b;
    for (vector<int> &group : groups) {
        for (int a : group) {
            for (int b : group) {
                if (a == b) {
                    break;
                }
                side_a.push_back(a);
                side_b.push_back(b);
            }
        }
    }
    vector<int> response = ask(side_a, side_b);

    for (int i = 0; i < side_a.size(); i++) {
        if (response[i] == side_a[i]) {
            _del_date[side_b[i]] = _cur_date;
        } else {
            _del_date[side_a[i]] = _cur_date;
        }
    }

    vector<int> res;
    for (vector<int> &group : groups) {
        for (int a : group) {
            if (_del_date[a] != _cur_date) {
                res.push_back(a);
            }
        }
    }
    return res;
}

#define ask
int richest(int N, int T, int S) {
    _cur_date++;
    vector<int> candidates(N);
    iota(candidates.begin(), candidates.end(), 0);
    for (int d = 0; d < 8; d++) {
        int before = levels[d], after = levels[d + 1];
        int div = before / after;
        int rem = before % after;

        assert(candidates.size() <= before);
        vector<vector<int>> groups;
        int idx = 0;
        for (int gi = 0; gi < after; gi++) {
            vector<int> group;
            for (int _i = gi >= rem; _i <= div; _i++) {
                if (idx == candidates.size()) break;
                group.push_back(candidates[idx++]);
            }
            groups.push_back(group);
        }
        candidates = query(groups);

        assert(candidates.size() <= after);
    }
    return candidates[0];
}
#undef ask