// 0 pts
#include <bits/stdc++.h>
#include "richest.h"
using namespace std;

const int N = 1000010;
int pos[N], cnt, nxt[N], tot, siz[N], fin[N];
int richest(int n, int t, int s)
{
	if(n <= 1000)
	{
		vector < int > a, b, c; int cnt[1010] = {0};
		for(int i = 0; i < n; ++i)
			for(int j = i + 1; j < n; ++j)
				a.push_back(i), b.push_back(j);
		c = ask(a, b);
		for(int i = 0; i < (int)c.size(); ++i) ++cnt[c[i]];
		for(int i = 0; i < n; ++i) if(cnt[i] == n - 1) return i;
	}
	else
	{
		int num[10] = {0, 2, 2, 2, 2, 3, 6, 19, 183};
		cnt = n;
		for(int i = 1; i <= cnt; ++i) pos[i] = i - 1;
		for(int i = 1; i <= 8; ++i)
		{
			int B = num[i];
			vector < int > a, b, c;
			for(int j = 0; j <= n; ++j) fin[j] = 0;
			for(int l = 1; l <= cnt; ++l)
			{
				int r = min(l + B - 1, cnt);
//				cerr << "! " << l << " " << r << '\n';
//				for(int j = l; j <= r; ++j) cerr << pos[j] << " "; cerr << '\n';
				for(int j = l; j <= r; ++j) siz[j] = r - l + 1;
				for(int p1 = l; p1 <= r; ++p1)
					for(int p2 = p1 + 1; p2 <= r; ++p2)
						a.push_back(pos[p1]), b.push_back(pos[p2]);
				l = r;
			}
			c = ask(a, b);
			for(int j = 0; j < (int)c.size(); ++j) ++fin[c[j]];
			tot = 0;
			for(int j = 1; j <= cnt; ++j)
			{
				if(fin[pos[j]] == siz[j] - 1)
				{
					nxt[++tot] = pos[j];
				}
			}
			cnt = tot;
			for(int j = 1; j <= cnt; ++j) pos[j] = nxt[j];
		}
		return pos[1];
	}
}
/*
1100043
2 2 2 2 3 6 19 183
*/