#include <bits/stdc++.h>
#include "richest.h"
#define rep(i,x,y) for(int i=x; i<=y; ++i)
#define repd(i,x,y) for(int i=x; i>=y; --i)

using namespace std;

int richest(int N, int T, int S) {
    vector<int> id(N);
    iota(id.begin(), id.end(), 0);

    auto query = [&](int p, int q) {
        vector<int> a, b;
        N = id.size();
        rep(i,0,q-1) {
            rep(j,0,p-1)
                rep(k,0,j-1) {
                    a.emplace_back(id[i * p + j]);
                    b.emplace_back(id[i * p + k]);
                }
        }
        int l = p * q;
        while(l + p - 1 < N) {
            rep(j,0,p-2)
                rep(k,0,j-1) {
                    a.emplace_back(id[l + j]);
                    b.emplace_back(id[l + k]);
                }
            l += p - 1;
        }
        rep(j,l,N-1)
            rep(k,l,j-1) {
                a.emplace_back(id[j]);
                b.emplace_back(id[k]);
            }
        return make_pair(a, b);
    };

    vector<bool> vis(N);
    auto kill = [&](vector<int> a, vector<int> b, vector<int> c) {
        rep(i,0,c.size()-1)
            vis[a[i]^b[i]^c[i]] = 1;
        vector<int> tmp;
        rep(i,0,N-1)
            if(!vis[id[i]])
                tmp.emplace_back(id[i]);
        id = move(tmp);
    };

    vector<pair<int, int>> ins {{2, 500000},
                            {2, 250000},
                            {2, 125000},
                            {2, 62500},
                            {4, 1},
                            {7, 1},
                            {19, 178},
                            {183, 1}};

    if (N == 1000)
        ins = {{N, 1}};

    for(auto [p, q] : ins) {
        auto [a, b] = query(p, q);
        auto c = ask(a, b);
        kill(a, b, c);
    }

    return id.back();
}