#include "richest.h"

constexpr int MAXN = 1000000;
constexpr int K[4] = {20832, 3472, 183, 1};

int cnt[MAXN];

void query1(std::vector<int> &q1, std::vector<int> &q2, std::vector<int> vec) {
    for (int i = 0; i < vec.size(); i ++) {
        for (int j = i + 1; j < vec.size(); j ++) {
            q1.push_back(vec[i]);
            q2.push_back(vec[j]);
        }
        cnt[vec[i]] = 0;
    }
}

std::vector<int> query2(std::vector<int> vec) {
    std::vector<int> v1, v2;

    for (int i = 0; i + 1 < vec.size(); i += 2) {
        v1.push_back(vec[i]);
        v2.push_back(vec[i + 1]);
    }

    std::vector<int> ret = ask(v1, v2);

    if (vec.size() & 1) {
        ret.push_back(vec.back());
    }

    return ret;
}

int richest(int N, int T, int S) {
    std::vector<int> cur, res, q1, q2;

    for (int i = 0; i < N; i ++) {
        cur.push_back(i);
    }

    if (T == 1) {
        query1(q1, q2, cur);
        res = ask(q1, q2);

        for (int v : res) {
            cnt[v] ++;
        }

        for (int i = 0; i < N; i ++) {
            if (cnt[i] == N - 1) {
                return i;
            }
        }      
    }

    for (int i = 0; i < 4; i ++) {
        cur = query2(cur);
    }

    for (int i = 0; i < 4; i ++) {
        int k = cur.size() / K[i];
        int r = cur.size() % K[i];

        std::vector<int> nxt;
        q1.clear();
        q2.clear();

        for (int j = 0, id = 0, len; j < cur.size(); j += len) {
            len = k + (id ++ < r);
            query1(q1, q2, std::vector<int>(cur.begin() + j, cur.begin() + j + len));
        }

        res = ask(q1, q2);

        for (int v : res) {
            cnt[v] ++;
        }

        for (int j = 0, id = 0, len; j < cur.size(); j += len) {
            len = k + (id ++ < r);

            for (int x = j; x < j + len; x ++) {
                if (cnt[cur[x]] == len - 1) {
                    nxt.push_back(cur[x]);
                }
            }
        }

        cur = nxt;
    }

    return cur.back();
}