#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);
    auto calc = [&](int k) {
        int x = A.size() / k;
        int y = (k - A.size() % k) % k;
        if (y) {
            ++x;
            x -= y;
        }
        vector<int> X, Y;
        rep (i, x) {
            rep (a, k) rep (b, a) {
                X.push_back(A[i * k + a]);
                Y.push_back(A[i * k + b]);
            }
        }
        rep (i, y) {
            rep (a, k - 1) rep (b, a) {
                X.push_back(A[x * k + i * (k - 1) + a]);
                Y.push_back(A[x * k + i * (k - 1) + b]);
            }
        }
        vector<int> Z = ask(X, Y);
        vector<int> B;
        int t1 = k * (k - 1) / 2;
        int t2 = (k - 1) * (k - 2) / 2;
        {
            rep (i, x) {
                map<int, int> mp;
                rep (j, k) mp[A[i * k + j]] += k - 1;
                rep (j, t1) --mp[Z[i * t1 + j]];
                for (auto [a, b] : mp) {
                    if (b == 0) B.push_back(a);
                }
            }
        }
        {
            rep (i, y) {
                map<int, int> mp;
                rep (j, k - 1) mp[A[x * k + i * (k - 1) + j]] += k - 2;
                rep (j, t2) --mp[Z[x * t1 + i * t2 + j]];
                for (auto [a, b] : mp) {
                    if (b == 0) B.push_back(a);
                }
            }
        }
        A = B;
    };
    rep (_, 4) calc(2);
    calc(3);
    calc(6);
    calc(19);
    calc(A.size());
    return A[0];
}