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

using namespace std;
using ll = long long;

int richest(int N, int T, int S) {
    vector<int> types{0, 0, 0, 0, 3, 6, 19, -1};
    if (T == 1) {
        types = {-1};
    }
    vector<int> a(N);
    iota(a.begin(), a.end(), 0);
    for (int x : types) {
        int n = a.size();
        if (x == 0) {
            vector<int> u, v;
            for (int i = 0; i < n; ++i) {
                (i % 2 ? v : u).push_back(a[i]);
            }
            int add = -1;
            if (u.size() > v.size()) {
                add = u.back();
                u.pop_back();
            }
            vector<int> res = ask(u, v);
            if (add != -1) {
                res.push_back(add);
            }
            a = res;
        } else if (x == -1) {
            vector<int> u, v;
            for (int i = 0; i < n; ++i) {
                for (int j = i + 1; j < n; ++j) {
                    u.push_back(a[i]);
                    v.push_back(a[j]);
                }
            }
            vector<int> res = ask(u, v);
            vector<int> cnt(N + 1);
            for (int &t : res) {
                cnt[t] += 1;
            }
            for (int t : a) {
                if (cnt[t] == n - 1) {
                    return t;
                }
            }
            assert(false);
            return -1;
        } else {
            int g = x;
            vector<int> u, v;
            for (int i = 0; i < n; ++i) {
                int nx = min(n, i / g * g + g);
                for (int j = i + 1; j < nx; ++j) {
                    u.push_back(a[i]);
                    v.push_back(a[j]);
                }
            }
            vector<int> res = ask(u, v);
            vector<int> cnt(N + 1), pos(N + 1, -1);
            for (int &t : res) {
                cnt[t] += 1;
            }
            for (int i = 0; i < n; ++i) {
                pos[a[i]] = i;
            }
            vector<int> l;
            int c = n / g;
            for (int t : a) {
                if (cnt[t] == g - 1) {
                    l.push_back(t);
                } else if (pos[t] / g >= c && cnt[t] == n % g - 1) {
                    l.push_back(t);
                }
            }
            a = l;
        }
        if (a.size() == 1) {
            break;
        }
    }
    return a[0];
}