#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")

#include <bits/stdc++.h>
#include "richest.h"

using namespace std;

const int N = 1000010, M = 1010;

int ns[] = {1000000, 500000, 250000, 125000, 62497, 20832, 3472, 183, 1};

int solve(int l, int r) {
	if (l == r) return l;
	int mid = (l+r)>>1;
	int x = solve(l, mid), y = solve(mid+1, r);
	return ask({x}, {y})[0];
}

int richest(int n, int k, int s) {
	if (n == (int)1e6) {
	vector <int> ans(N);
	for (int i = 0; i < N; i++) ans[i] = i;
	for (int t = 0; t < 8; t++) {
		int n1 = ns[t], n2 = ns[t+1];
		int a1 = n1/n2, a2 = a1+1;
		int c2 = n1%n2, c1 = n2-c2;
		int m = 1ll*a1*(a1-1)/2*c1+1ll*a2*(a2-1)/2*c2;
		vector<int> a, b;
		for (int i = 0, k = 0, l = 0; i < n2; i++) {
			int r = l;
			if (k < c1) k++, r += a1;
			else r += a2;
			for (int j = l; j < r; j++) {
				for (int p = j+1; p < r; p++) {
					a.push_back(ans[j]);
					b.push_back(ans[p]);
				}
			}
			l = r;
		}
		vector <int> c = ask(a, b);
		vector <int> val(n2);
		for (int i = 0, k = 0, l = 0, t = 0; i < n2; i++) {
			int r = l;
			if (k < c1) k++, r += a1;
			else r += a2;
			static int cnt[N];
			for (int j = l; j < r; j++) cnt[ans[j]] = 0;
			for (int j = l; j < r; j++) {
				for (int p = j+1; p < r; p++) {
					cnt[c[t]]++, t++;
				}
			}
			for (int j = l; j < r; j++) {
				if (cnt[ans[j]] == r-l-1) val[i] = ans[j];
			}
			l = r;
		}
		ans.swap(val);
	}
	return ans[0];
	} // Test #2
	
	return solve(0, n-1);
}

//int main() {
//	
//	return 0;
//}