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

constexpr int table[] = {1000000, 500000, 250000, 125000, 62500, 20832, 3472, 183, 1};

constexpr int N = 1000006;

int cnt[N];
std::vector<int> a, b, c;
void query(std::vector<int> vec) {
    for (int i = 0; i < vec.size(); i++)
    for (int j = i + 1; j < vec.size(); j++) {
        a.push_back(vec[i]);
        b.push_back(vec[j]);
    }
}

int richest(int n, int t, int s) {
    std::fill_n(cnt, n, 0);
    std::vector<int> all(n);
    std::iota(all.begin(), all.end(), 0);
    const auto work = [&](int len) {
        int t = all.size() / len, w = all.size() % len;
        a.clear();
        b.clear();
        for (int i = 0, l = 0, r; i < len; i++, l = r) {
            r = l + t + (i < w);
            query(std::vector<int>(all.begin() + l, all.begin() + r));
        }
        c = ask(a, b);
        for (int i = 0; i < a.size(); i++) cnt[a[i] ^ b[i] ^ c[i]]++;
        std::vector<int> _all;
        for (int x : all) if (!cnt[x]) _all.push_back(x);
        std::swap(all, _all);
    };
    if (n == 1000) work(1);
    else for (int i = 1; i <= 8; i++) work(table[i]);
    return all[0];
}