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

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep2(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); --i)

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)

using namespace std;

using ll = long long;
using ull = unsigned long long;

template<class T, class U> bool chmin(T& a, const U& b) { return a > b ? a = b, true : false; }
template<class T, class U> bool chmax(T& a, const U& b) { return a < b ? a = b, true : false; }

constexpr ll inf = 1001001001001001001;

int richest(int N, int T, int S) {
    if (T == 1) {
        vector<int> a, b;
        rep (i, N) rep (j, i) a.push_back(i), b.push_back(j);
        auto c = ask(a, b);
        vector<bool> used(N);
        rep (i, a.size()) used[a[i] ^ b[i] ^ c[i]] = true;
        rep (i, N) {
            if (!used[i]) return i;
        }
        return -1;
    }
    vector<int> A(N); iota(all(A), 0);
    int sm = 0;
    while (A.size() > 125000) {
        vector<int> X, Y;
        rep (i, A.size() / 2) {
            X.push_back(A[i * 2]);
            Y.push_back(A[i * 2 + 1]);
        }
        sm += X.size();
        vector<int> B = ask(X, Y);
        if (A.size() % 2 == 1) B.push_back(A.back());
        A = B;
    }
    while (A.size() > 14000) {
        vector<int> X, Y;
        rep (i, A.size() / 3) {
            rep (k, 3) X.push_back(A[i * 3 + k % 3]);
            rep (k, 3) Y.push_back(A[i * 3 + (k + 1) % 3]);
        }
        if (A.size() % 3 == 2) {
            X.push_back(A[A.size() - 2]);
            Y.push_back(A[A.size() - 1]);
        }
        if (A.size() % 3 == 1) A = {A.back()};
        else A.clear();
        sm += X.size();
        auto B = ask(X, Y);
        rep (i, B.size() / 3) {
            if (B[i * 3] == B[i * 3 + 1]) A.push_back(B[i * 3]);
            else if (B[i * 3 + 1] == B[i * 3 + 2]) A.push_back(B[i * 3 + 1]);
            else A.push_back(B[i * 3 + 2]);
        }
        if (B.size() % 3 == 1) A.push_back(B.back());
    }
    while (A.size() > 300) {
        vector<int> X, Y;
        rep (i, A.size() / 4) {
            rep (k, 4) rep (l, k) {
                X.push_back(A[i * 4 + k]);
                Y.push_back(A[i * 4 + l]);
            }
        }
        if (A.size() % 4 == 3) {
            X.push_back(A[A.size() - 3]);
            X.push_back(A[A.size() - 2]);
            X.push_back(A[A.size() - 1]);
            Y.push_back(A[A.size() - 2]);
            Y.push_back(A[A.size() - 1]);
            Y.push_back(A[A.size() - 3]);
        }
        if (A.size() % 4 == 2) {
            X.push_back(A[A.size() - 2]);
            Y.push_back(A[A.size() - 1]);
        }
        if (A.size() % 4 == 1) A = {A.back()};
        else A.clear();
        sm += X.size();
        auto B = ask(X, Y);
        rep (i, B.size() / 6) {
            map<int, int> mp;
            rep (j, 6) ++mp[B[i * 6 + j]];
            for (auto [x, v] : mp) {
                if (v == 3) A.push_back(x);
            }
        }
        if (B.size() % 6 == 1) A.push_back(B.back());
        else if (B.size() % 6 == 3) {
            map<int, int> mp;
            rep (j, 3) ++mp[B[B.size() - 3 + j]];
            for (auto [x, v] : mp) {
                if (v == 2) A.push_back(x);
            }
        }
    }
    if (A.size() == 1) return A[0];
    vector<int> X, Y;
    rep (i, A.size()) rep (j, i) {
        X.push_back(A[i]);
        Y.push_back(A[j]);
    }
    auto B = ask(X, Y);
    map<int, int> mp;
    for (int i : B) ++mp[i];
    for (auto [x, v] : mp) {
        if (v == A.size() - 1) return x;
    }
    return -1;
}