#include "richest.h"

int richest(int N, int T, int S) {
    if (T == 1 && S >= (long long)N * (N - 1) / 2) {
        int m = N * (N - 1) / 2;
        std::vector<int> a, b;
        a.reserve(m);
        b.reserve(m);
        for (int i = 0; i < N; ++i)
            for (int j = i + 1; j < N; ++j)
                a.push_back(i),
                b.push_back(j);
        auto c = ask(a, b);
        std::vector<int> win(N, 0);
        for (int i = 0; i < m; ++i)
            ++win[c[i]];
        for (int i = 0; i < N; ++i)
            if (win[i] == N - 1)
                return i;
    }
    // N == 1000000
    const int ns[] = {1000000, 500000, 250000, 125000, 62497, 20832, 3472, 183, 1};
    std::vector<int> cand(N);
    for (int i = 0; i < N; ++i)
        cand[i] = i;
    for (int t_ = 0; t_ < 8; ++t_) {
        int n1 = ns[t_], n2 = ns[t_ + 1];
        int a1 = n1 / n2;
        int a2 = a1 + 1;
        int c2 = n1 % n2;
        int c1 = n2 - c2;
        int m = a1 * (a1 - 1) / 2 * c1 + a2 * (a2 - 1) / 2 * c2;
        std::vector<int> a, b;
        a.reserve(m), b.reserve(m);
        for (int i = 0, j1 = 0, k = 0; i < n2; ++i) {
            int j2 = j1 + (k < c1 ? (++k, a1) : a2);
            for (int j = j1; j < j2; ++j)
                for (int j_ = j + 1; j_ < j2; ++j_)
                    a.push_back(cand[j]),
                    b.push_back(cand[j_]);
            j1 = j2;
        }
        auto c = ask(a, b);
        std::vector<int> ncand(n2);
        for (int i = 0, j1 = 0, k = 0, p = 0; i < n2; ++i) {
            int j2 = j1 + (k < c1 ? (++k, a1) : a2);
            static int win[1000000];
            for (int j = j1; j < j2; ++j)
                win[cand[j]] = 0;
            for (int j = j1; j < j2; ++j)
                for (int j_ = j + 1; j_ < j2; ++j_)
                    ++win[c[p++]];
            for (int j = j1; j < j2; ++j)
                if (win[cand[j]] == j2 - j1 - 1)
                    ncand[i] = cand[j];
            j1 = j2;
        }
        cand.swap(ncand);
    }
    return cand[0];
}