#include "richest.h"
#include <bits/stdc++.h>
using namespace std;
inline long long read(){
	long long x=0; char ch; bool f=0;
	while(((ch=getchar())<'0'||ch>'9')&&ch!='-') ;
	if(ch=='-') f=1;
	else x=ch^48;
	while((ch=getchar())>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48);
	return f?-x:x;
}
//int T,S;
//std::vector<int> ask(std::vector<int> a, std::vector<int> b){
//	T++;
//	vector<int> c;
//	for(int i=0;i<a.size();i++){
//		S++;
//		c.push_back(max(a[i],b[i]));
//	}
//	return c;
//}
const int dx[10]={1,183,3472,20832,62496,125000,250000,500000};
const int N=1e6+5;
long long f[12][N],lst[12][N];
long long calc(int n,int m){
	if(n==m) return 0;
	long long t=n/m,t2=n-t*m;
	return (m-t2)*t*(t-1)/2+t2*(t+1)*t/2;
}
int ct[N];
int richest(int n,int T,int S){
	for(int i=0;i<n;i++) ct[i]=0;
	if(n<=1000){
		vector<int> a,b;
		for(int i=0;i<n;i++){
			for(int j=i+1;j<n;j++) a.push_back(i),b.push_back(j);
		}
		vector<int> c=ask(a,b);
		for(int i=0;i<c.size();i++){
			if(c[i]==a[i]) ct[b[i]]=1;
			else ct[a[i]]=1;
		}
		for(int i=0;i<n;i++){
			if(!ct[i]) return i;
		}
	}
	vector<int> s;
	for(int i=0;i<n;i++) s.push_back(i);
	for(int i=7;i>=0;i--){
		vector<int> a,b;
		int m=dx[i]; 
		long long t=n/m,t2=n-t*m;
		int st=0;
		for(int j=1;j<=m-t2;j++){
			for(int t1=st;t1<st+t;t1++){
				for(int t2=t1+1;t2<st+t;t2++){
					a.push_back(s[t1]),b.push_back(s[t2]);
				}
			}
			st+=t;
		}
		for(int j=m-t2+1;j<=m;j++){
			for(int t1=st;t1<st+t+1;t1++){
				for(int t2=t1+1;t2<st+t+1;t2++){
					a.push_back(s[t1]),b.push_back(s[t2]);
				}
			}
			st+=t+1;
		}
		vector<int> c=ask(a,b);
		vector<int> ss;
		st=0; int cnt=0;
		for(int j=1;j<=m-t2;j++){
			for(int t1=st;t1<st+t;t1++) ct[s[t1]]=0;
			for(int t1=st;t1<st+t;t1++){
				for(int t2=t1+1;t2<st+t;t2++){
					if(c[cnt]==a[cnt]) ct[b[cnt]]=1;
					else ct[a[cnt]]=1;
					cnt++;
				}
			}
			for(int t1=st;t1<st+t;t1++){
				if(!ct[s[t1]]){
					ss.push_back(s[t1]);
					break;
				}
			}
			st+=t;
		}
		for(int j=m-t2+1;j<=m;j++){
			for(int t1=st;t1<st+t+1;t1++) ct[s[t1]]=0;
			for(int t1=st;t1<st+t+1;t1++){
				for(int t2=t1+1;t2<st+t+1;t2++){
					if(c[cnt]==a[cnt]) ct[b[cnt]]=1;
					else ct[a[cnt]]=1;
					cnt++;
				}
			}
			for(int t1=st;t1<st+t+1;t1++){
				if(!ct[s[t1]]){
					ss.push_back(s[t1]);
					break;
				}
			}
			st+=t+1;
		}
		n=dx[i];
		swap(s,ss);
	}
	return s[0];
}
//int main(){
//	T=0,S=0; int n=1e6;
//	cout<<richest(n,0,0)<<"\n??"<<T<<" "<<S<<"!\n";
//}