/*
*            /$$           /$$
*           |__/          |__/
*  /$$$$$$$$ /$$ /$$$$$$$$ /$$  /$$$$$$
* |____ /$$/| $$|____ /$$/| $$ /$$__  $$
*    /$$$$/ | $$   /$$$$/ | $$| $$  \ $$
*   /$$__/  | $$  /$$__/  | $$| $$  | $$
*  /$$$$$$$$| $$ /$$$$$$$$| $$|  $$$$$$$
* |________/|__/|________/|__/ \____  $$
*                                   | $$
*                                   | $$
*                                   |__/
*/
//hj23308保佑我
//Missile保佑我
/*
* 醒了在梦里挣扎，不觉黯淡了朝霞
*/
/*
* 我很高兴你没有忘了我，但是我现在更希望你已经忘了我了。
* 希望在你的记忆中，我只是尘土一撮，从你的全世界路过，然后四散飞扬不留下一点痕迹，而你要不回头的往前走。
* 我更希望我只是从你的全世界路过，只是路过
*/
/*
* 只是我在十字路口守了太久，守到黄沙如雨掩埋一切痕迹，才发现自己等的人已经离开了。
*/
/*
* 听我的 别回头 回头就可能会泪流满面，会被黄沙掩埋，所以即使痛苦也要向前走
*/
/*
* 我听到了「天行健」的回响，这是一个伟大斗士的不息自强；
* 我听到了「破万法」的回响，这是一个黑道打手的守护欲望；
* 我看见了「生生不息」的激荡，这是一个骗子的伟大乐章！
*/
/*
* 我用虚假的面具照顾着细腻的感情；
* 我以华丽的衣物下藏着腐烂的血肉；
* 当我摘下面具，褪去衣物，即便是我最亲近的人，也无法直视我
*/
#include<bits/stdc++.h>
#include "richest.h"
using namespace std;
const int MAXN=1e6+5;
int num[MAXN];
bool bj[MAXN];
int Snum=0,Tnum=0;
int Len[MAXN],L[MAXN],R[MAXN];
int K[9]={0,500000,250000,125000,62500,20832,3472,183,1};
void clear(int N)
{
	for(int i=0;i<N;i++) num[i]=0;
}
//vector<int>ask(vector<int>a,vector<int>b) {
//	Tnum++;
//	Snum+=a.size();
//	vector<int>c;
//	for(int i=0;i<a.size();i++) {
//		c.emplace_back(max(a[i],b[i]));
//	}
//	return c;
//}
int richest(int N,int T,int S)
{
	vector<int>a,b,c;
	if(N==1000&&T==1) {
		clear(N);
		a.clear(),b.clear(),c.clear();
		for(int i=0;i<N;i++) {
			for(int j=i+1;j<N;j++) {
				a.emplace_back(i),b.emplace_back(j);
			}		
		}
		c=ask(a,b);
		for(auto v:c) {
			num[v]++;
		}
		for(int i=0;i<N;i++) {
			if(num[i]==N-1) return i;
		}
	}
	vector<int>q;
	for(int i=0;i<N;i++) q.emplace_back(i);
	for(int i=0;i<N;i++) bj[i]=false;
	for(int site=1;site<=8;site++) {
		int k=K[site],siz=q.size();
		for(int i=1;i<=k;i++) {
			Len[i]=siz/k;
		}
		for(int i=1;i<=siz%k;i++) {
			Len[i]++;
		}
		R[0]=-1;
		for(int i=1;i<=k;i++) {
			L[i]=R[i-1]+1,R[i]=L[i]+Len[i]-1;
		}
		a.clear(),b.clear();
		for(int i=1;i<=k;i++) {
			for(int j=L[i];j<=R[i];j++) {
				for(int xk=j+1;xk<=R[i];xk++) {
					a.emplace_back(q[j]);
					b.emplace_back(q[xk]);
				}
			}
		}
		c=ask(a,b);
		clear(N);
		for(auto v:c) {
			num[v]++;
		}
		for(int i=1;i<=k;i++) {
			for(int j=L[i];j<=R[i];j++) {
				if(num[q[j]]!=Len[i]-1) {
					bj[q[j]]=true;
				}
			}
		}
		q.clear();
		for(int i=0;i<N;i++) {
			if(!bj[i]) q.emplace_back(i);
		}
	}
//	cout<<Snum<<" "<<Tnum<<"\n";
	return q[0];
}
//int main()
//{
//	cout<<richest(1000000,20,2000000)<<"\n";
//}