#include "richest.h"
#include <bits/stdc++.h>
using namespace std;
using vint = vector<int>;

const int B[10] = {0, 500000, 250000, 125000, 62500, 20833, 3472, 183};

int solve(vint v, int N) {
	vint a, b;
	for (int i = 1; i < v.size(); ++i) {
		for (int j = 0; j < i; ++j) {
			a.push_back(v[i]), b.push_back(v[j]);
		}
	}
	
	vint c = ask(a, b), cnt(N);
	for (auto &u: c) cnt[u]++;
	for (auto &u: v) if (cnt[u] == (int)v.size() - 1) return u;
	return -1;
}

int richest(int N, int T, int S) {
	if (N <= 1000) {
		vint v(N);
		for (int i = 0; i < N; ++i) v[i] = i;
		return solve(v, N);
	}	
	
	vint v(N);
	for (int i = 0; i < N; ++i) v[i] = i;
	
	int k = 1;
	while (k <= 7) {
		vint len(B[k], v.size() / B[k]);
		for (int i = 0; i < v.size() % B[k]; ++i) len[i]++;
		vint a, b;
		for (int i = 0, l = 0, r; i < B[k]; ++i, l = r + 1) {
			r = l + len[i] - 1;
			for (int j = l + 1; j <= r; ++j) {
				for (int k = l; k < j; ++k) {
					a.push_back(v[j]), b.push_back(v[k]);
				}
			}
		}
		
		vint c = ask(a, b), cnt(N);
		for (int i = 0; i < c.size(); ++i) cnt[a[i] ^ b[i] ^ c[i]]++;
		
		vint nv;
		for (auto &u: v) if (!cnt[u]) nv.push_back(u); 
		++k, swap(v, nv);
	}
	
	return solve(v, N);
}