#include <iostream>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include <bits/stdc++.h>

#include "richest.h"

const std::string precalc_str_data = R"(
15
1 2  1 -1 -1
1 3  3 -1 -1
1 4  6 -1 -1
1 6  15 -1 -1
1 18  153 -1 -1
1 19  171 -1 -1
1 183  16653 -1 -1
2 4  3 2 1
2 18  33 6 1
2 19  36 6 1
2 3472  47856 183 1
3 8  7 2 1
4 16  15 2 1
4 62500  162444 3472 2
8 1000000  1099944 62500 4
)";

std::vector<int> select_multi(int t, const std::vector<std::vector<int>>& vec) {
    if (t == 1) {
        std::vector<int> a, b;
        for (int i = 0; i < vec.size(); i++) {
            auto& vc = vec[i];
            for (int i = 0; i < vc.size(); i++) {
                for (int j = i + 1; j < vc.size(); j++) {
                    a.push_back(vc[i]);
                    b.push_back(vc[j]);
                }
            }
        }
        std::vector<int> c = ask(a, b);
        // std::sort(c.begin(), c.end());
        std::unordered_map<int, int> map;
        for (auto& i : c) {
            map[i]++;
        }
        auto count = [&](int val) {
            return map[val];
            // auto [it1, it2] = std::equal_range(c.begin(), c.end(), val);
            // return it2 - it1;
        };
        std::vector<int> ans(vec.size());
        for (int i = 0; i < vec.size(); i++) {
            ans[i] = vec[i].front();
            for (int j : vec[i]) {
                if (count(j) > count(ans[i])) {
                    ans[i] = j;
                }
            }
        }
        return ans;
    } else {
        std::map<std::pair<int, int>, std::array<int64_t, 3>> map;
        {
            std::stringstream sin(precalc_str_data);
            int cnt;
            sin >> cnt;
            for (int i = 0; i < cnt; i++) {
                int64_t a, b, c, d, e;
                sin >> a >> b >> c >> d >> e;
                if (a == 1) {
                    continue;
                }
                map[{a, b}] = {c, d, e};
            }
        }
        std::vector<std::vector<std::vector<int>>> vec2(vec.size());
        int tt = -1;
        for (int i = 0; i < vec.size(); i++) {
            auto& vc = vec[i];
            assert(map.contains({t, (int)vc.size()}));
            auto [cnt, k, t2] = map[{t, (int)vc.size()}];
            if (tt == -1) {
                tt = t2;
            } else {
                assert(tt == t2);
            }
            std::vector<std::vector<int>> vc2(k);
            for (int i = 0; i < vc.size(); i++) {
                vc2[i % k].push_back(vc[i]);
            }
            vec2[i] = std::move(vc2);
        }
        std::vector<std::vector<int>> vec2_f;
        for (int i = 0; i < vec2.size(); i++) {
            vec2_f.insert(vec2_f.end(), vec2[i].begin(), vec2[i].end());
        }

        std::vector<int> ans0 = select_multi(t - tt, vec2_f);

        std::vector<std::vector<int>> vec3(vec.size());
        for (int i = 0, ind = 0; i < vec.size(); i++) {
            std::vector<int> vc(ans0.begin() + ind, ans0.begin() + ind + vec2[i].size());
            vec3[i] = std::move(vc);
            ind += vec2[i].size();
        }

        std::vector<int> ans = select_multi(tt, vec3);
        return ans;
    }
    assert(false);
}

int richest(int n, int t, int s) {
    t = std::min(t, 8);
    std::vector<int> all(n);
    std::iota(all.begin(), all.end(), 0);
    auto ans = select_multi(t, {all});
    assert(ans.size() == 1);
    return ans.front();
}

// 100 1 100000 5
// 1000000 20 1500000 123

// ! precalc code
/*

#include <bits/stdc++.h>

constexpr int64_t inf = 1e18;

int32_t main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    const int T = 8;
    const int N = 1e6;
    std::vector<std::vector<std::pair<int64_t, std::pair<int, int>>>> dp(T + 1, std::vector<std::pair<int64_t, std::pair<int, int>>>(N + 2, {inf, {-1, -1}}));

    dp[0][1] = {0, {-1, -1}};
    for (int t = 1; t <= T; t++) {
        auto get = [&](int i, int k) {
            auto [q, r] = div(i, k);

            int64_t min = inf;
            int tm = -1;
            for (int t2 = 1; t2 < t; t2++) {
                int64_t val = 0;
                val += int64_t(k - r) * dp[t - t2][q].first;
                val += int64_t(r) * dp[t - t2][q + 1].first;
                val += dp[t2][k].first;
                if (val < min) {
                    min = val;
                    tm = t2;
                }
            }

            return std::pair{min, std::pair{k, tm}};
        };

        for (int i = 1; i <= N; i++) {
            if (t == 1) {
                dp[t][i] = {int64_t(i - 1) * i / 2, {-1, -1}};
                continue;
            }
            dp[t][i] = dp[t - 1][i];
            if (t == T && i != N) {
                continue;
            }
            if (i != N && i > 1e5) {
                continue;
            }
            for (int k = 1; k <= i; k++) {
                dp[t][i] = std::min(dp[t][i], get(i, k));
            }
        }
        std::cout << t << " " << dp[t][N].first << " " << dp[t][N].first / 1e6 << "M " << dp[t][N].second.first << " " << dp[t][N].second.second << std::endl;
    }

    std::vector<std::vector<bool>> used(T + 1, std::vector<bool>(N + 2, false));

    std::map<std::pair<int, int>, std::remove_reference<decltype(dp[0][0])>::type> map;
    auto fuck = [&](auto fuck, int t, int i) -> void {
        if (t < 0) {
            return;
        }
        if (!used[t][i]) {
            used[t][i] = true;
            map[std::pair<int, int>{t, i}] = dp[t][i];
            auto [k, t2] = dp[t][i].second;
            if (k <= 0) {
                return;
            }
            auto [q, r] = div(i, k);
            fuck(fuck, t - t2, q);
            if (r) {
                fuck(fuck, t - t2, q + 1);
            }
            fuck(fuck, t2, k);
        }
    };
    fuck(fuck, T, N);

    std::ofstream fout("data_3.txt");
    fout << map.size() << "\n";
    for (auto [id, val] : map) {
        fout << id.first << " " << id.second << "  " << val.first << " " << val.second.first << " " << val.second.second << std::endl;
    }

    return 0;
}


*/