#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, 31250, 15625, 5209, 882, 47, 1 }, cnt[maxn];
int richest(int n, int t, int s) {
	vec a; 
	for (int i = 0; i < n; i++) a.push_back(i);
	for (int i = 0; i < min(10, 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];
}