#include <bits/stdc++.h>
#include "richest.h"
#define ll int
#define ull unsigned ll
#define pb push_back
using namespace std;
const ll maxn = 1e6 + 10, mod = 998244353;
ll n = 1e6, a[9] = {1000000, 500000, 250000, 125000, 62496, 20832, 3472, 183, 1};
vector <ll> v1, v2, reply;
ll fail[maxn], id[maxn], pid[maxn];
ll richest(ll N, ll T, ll S) {
	if(N <= 1000) {
		v1.clear(), v2.clear();
		for(ll i = 1; i <= N; i++) fail[i] = 0;
		for(ll i = 1; i <= N; i++)
			for(ll j = i + 1; j <= N; j++)
				v1.pb(i - 1), v2.pb(j - 1);
		reply = ask(v1, v2);
		ll p = 0;
		for(ll i = 1; i <= N; i++)
			for(ll j = i + 1; j <= N; j++)
				fail[(reply[p++] + 1) ^ i ^ j] = 1;
		for(ll i = 1; i <= N; i++)
			if(fail[i] == 0) return i - 1;
	}
	for(ll i = 1; i <= n; i++) id[i] = i;
	for(ll i = 1; i <= 8; i++) {
		for(ll j = 1; j <= n; j++) fail[j] = 0;
		ll t = a[i - 1] / a[i], u = a[i - 1] % a[i];
		ll p1 = a[i] - u, p2 = u;
		v1.clear(), v2.clear();
		for(ll j = 1; j <= p1; j++) {
			ll l = (j - 1) * t + 1, r = j * t;
			for(ll x = l; x <= r; x++)
				for(ll y = x + 1; y <= r; y++)
					v1.pb(id[x] - 1), v2.pb(id[y] - 1);
//			printf("[%d, %d]\n", l, r);
		}
		for(ll j = 1; j <= p2; j++) {
			ll l = (j - 1) * (t + 1) + 1, r = j * (t + 1);
			l += p1 * t, r += p1 * t;
			for(ll x = l; x <= r; x++)
				for(ll y = x + 1; y <= r; y++)
					v1.pb(id[x] - 1), v2.pb(id[y] - 1);
//			printf("[%d, %d]\n", l, r);
		} reply = ask(v1, v2); ll p = 0, e = 0;
		for(ll j = 1; j <= p1; j++) {
			ll l = (j - 1) * t + 1, r = j * t;
			for(ll x = l; x <= r; x++)
				for(ll y = x + 1; y <= r; y++)
					fail[id[x] ^ id[y] ^ (reply[p++] + 1)] = 1;
			for(ll x = l; x <= r; x++)
				if(fail[id[x]] == 0) pid[++e] = id[x];
		}
		for(ll j = 1; j <= p2; j++) {
			ll l = (j - 1) * (t + 1) + 1, r = j * (t + 1);
			l += p1 * t, r += p1 * t;
			for(ll x = l; x <= r; x++)
				for(ll y = x + 1; y <= r; y++)
					fail[id[x] ^ id[y] ^ (reply[p++] + 1)] = 1;
			for(ll x = l; x <= r; x++)
				if(fail[id[x]] == 0) pid[++e] = id[x];
		}
		for(ll j = 1; j <= a[i]; j++) id[j] = pid[j];
	} return id[1] - 1;
}