#include<bits/stdc++.h>
#include"richest.h"
using namespace std;
vector<int>ask(vector<int>a,vector<int>b);
namespace DZY{
//==========
const int max_n=1000000;
int n;
map<int,int>g[max_n+2];
const int si[12]={0,2,2,2,2,3,6,19,183};
vector<int>now;
vector<int>to;
vector<int>opa,opb;
int sumsi=0;
int ans=0;
void query(vector<int>a,vector<int>b){
	vector<int>res=ask(a,b);
	for(int i=0,len=res.size();i<len;++i)g[a[i]][b[i]]=res[i];
	sumsi+=res.size();
}
void askans(){
	sumsi=0;
	for(int i=0;i<=n;++i){g[i].clear(); g[i][i]=i;}
	if(n==1000){
		for(int i=0;i<n;++i){
			for(int j=i+1;j<n;++j){opa.push_back(i); opb.push_back(j);}
		}
		query(opa,opb);
		ans=0;
		for(int i=1;i<n;++i)ans=g[ans][i];
		return;
	}
	now.clear(); to.clear();
	for(int i=0;i<n;++i)now.push_back(i);
	for(int ca=1,len;ca<=8;++ca){
		len=now.size();
		opa.clear(); opb.clear();
		if(ca!=7){
			for(int l=0,r;l<len;l=r+1){
				if(len-l>=si[ca]*2)r=l+si[ca]-1;
				else r=len-1;
				for(int i=l;i<=r;++i){
					for(int j=i+1;j<=r;++j){opa.push_back(now[i]); opb.push_back(now[j]);}
				}
			}
		}
		else{
			for(int ca=0,l,r;ca<5;++ca){
				l=ca*18,r=l+17;
				for(int i=l;i<=r;++i){
					for(int j=i+1;j<=r;++j){opa.push_back(now[i]); opb.push_back(now[j]);}
				}
			}
			for(int ca=0,l,r;ca<178;++ca){
				l=90+ca*19,r=l+18;
				for(int i=l;i<=r;++i){
					for(int j=i+1;j<=r;++j){opa.push_back(now[i]); opb.push_back(now[j]);}
				}
			}
		}
		query(opa,opb);
		to.clear();
		if(ca!=7){
			for(int l=0,r,x;l<len;l=r+1){
				if(len-l>=si[ca]*2)r=l+si[ca]-1;
				else r=len-1;
				x=now[l];
				for(int i=l+1;i<=r;++i)x=g[x][now[i]];
				to.push_back(x);
			}
		}
		else{
			for(int ca=0,l,r,x;ca<5;++ca){
				l=ca*18,r=l+17;
				x=now[l];
				for(int i=l+1;i<=r;++i)x=g[x][now[i]];
				to.push_back(x);
			}
			for(int ca=0,l,r,x;ca<178;++ca){
				l=90+ca*19,r=l+18;
				x=now[l];
				for(int i=l+1;i<=r;++i)x=g[x][now[i]];
				to.push_back(x);
			}
		}
		now=to;
		printf("ca=%d sumsi=%d\n",ca,sumsi);
	}
	ans=now[0];
}
//==========
}
int richest(int N,int T,int S){
	DZY::n=N; DZY::askans(); return DZY::ans;
}