#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{500000,250000,125000,62500,20833,3472,183,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 > n) {
            continue;
        }
        vector<int> ax, ay;
        for (int i = 0, g = 0; i < n; ++g) {
            int siz = n / x + (n % x > g);
            for (int j = i; j < i + siz; ++j) {
                for (int z = j + 1; z < i + siz; ++z) {
                    ax.push_back(a[j]);
                    ay.push_back(a[z]);
                }
            }
            i += siz;
        }
        auto az = ask(ax, ay);
        vector<int> del(N);
        for (int i = 0; i < ax.size(); ++i) {
            del[ax[i] ^ ay[i] ^ az[i]] = true;
        }
        vector<int> nxt;
        for (int i : a) {
            if (!del[i]) {
                nxt.push_back(i);
            }
        }
        a = nxt;
        if (a.size() == 1) {
            break;
        }
    }
    return a[0];
}