#include <bits/stdc++.h>
//#include <windows.h>
using namespace std;
#include "richest.h"
#define rep(i, a, b) for(int i = a; i <= b; i++)
using vec = vector<int>;
using ll = long long int;
constexpr int maxn = 2e6 + 10;
#define ps push_back
int p[35] = { 500000, 250000, 125000, 62500, 20834, 3472, 348, 7, 1 }, cnt[maxn];
int richest(int n, int t, int s) {
	if (n <= 1000) {
		vec x, y, z;
		for (int i = 0; i < n - 1; i++) {
			for (int j = i + 1; j < n; j++) x.ps(i), y.ps(j);
		}
		z = ask(x, y); int ans = 0;
		for (int i = 0; i < z.size(); i++) {
			++cnt[z[i]];
			if (cnt[z[i]] == n - 1) ans = z[i];
		}
		for (int i = 0; i < z.size(); i++) --cnt[z[i]];
		return ans;
	}
	vec a; 
	for (int i = 0; i < n; i++) a.push_back(i);
	for (int i = 0; i < t; i++) {
		vec x, y;
		for (int j = 0; j < a.size(); j++) {
			for (int k = j % p[i]; k < j; k += p[i]) if (j != k) x.ps(a[j]), y.ps(a[k]);
		}
		vec z = ask(x, y), na;
		for (int j = 0; j < z.size(); j++) z[j] == x[j] ? ++cnt[y[j]] : ++cnt[x[j]];
		for (int j = 0; j < a.size(); j++) if (!cnt[a[j]]) na.ps(a[j]);
		for (int j = 0; j < z.size(); j++) z[j] == x[j] ? --cnt[y[j]] : --cnt[x[j]];
		a = na; 
	}
	return a[0];
}