#include <bits/stdc++.h>
#include "richest.h"
using namespace std;
int K[] = { 0, 500000, 250000, 125000, 62500, 20833, 3472, 183, 1 };
vector<int> Div(vector<int> a, int k) {
	int n = a.size(), p = 0, s = n / k;
	vector<int> x, y;
	for (int i = 0; i < n % k; i++) {
		for (int j = p; j < p + s + 1; j++) {
			for (int k = j + 1; k < p + s + 1; k++) {
				x.push_back(a[j]), y.push_back(a[k]);
			}
		}
		p += s + 1;
	}
	for (int i = 0; i < k - n % k; i++) {
		for (int j = p; j < p + s; j++) {
			for (int k = j + 1; k < p + s; k++) {
				x.push_back(a[j]), y.push_back(a[k]);
			}
		}
		p += s;
	}
	assert(p == n);
	p = 0;
	vector<int> c = ask(x, y), res;
	int cp = 0;
	for (int i = 0; i < n % k; i++) {
		int u = a[p];
		for (int j = p; j < p + s + 1; j++) {
			for (int k = j + 1; k < p + s + 1; k++) {
				int v = c[cp++];
				if (a[j] == u && a[k] == v) u = v;
			}
		}
		p += s + 1;
		res.push_back(u);
	}
	for (int i = 0; i < k - n % k; i++) {
		int u = a[p];
		for (int j = p; j < p + s; j++) {
			for (int k = j + 1; k < p + s; k++) {
				int v = c[cp++];
				if (a[j] == u && a[k] == v) u = v;
			}
		}
		p += s;
		res.push_back(u);
	}
	return res;
}
int richest(int N, int T, int S) {
	vector<int> a;
	for (int i = 0; i < N; i++) a.push_back(i);
	if (N == 1000) a = Div(a, 1);
	else {	
		for (int i = 1; i <= 8; i++) a = Div(a, K[i]);
	}
    return a[0];
}