#include "richest.h"
#include<bits/stdc++.h>
 
using namespace std;
 
std::vector <int> ask(std::vector <int> a, std::vector <int> b);

namespace sub1{
	const int maxn=1010;
	int id[maxn];
	bool win[maxn][maxn];

	inline int sol(int n){
		vector<int> a,b,c;
		for(int i=0;i<n;i++) id[i]=i;
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				win[i][j]=false;
		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<a.size();i++){
			int x=a[i],y=b[i],z=c[i];
			if(z==x) win[x][y]=true;
			else win[y][x]=true;
		} 
		for(int i=0;i<n;i++)
			for(int j=i+1;j<n;j++)
				if(win[id[i]][id[j]]) swap(id[i],id[j]);  
		return id[n-1];		
	}
}

namespace sub2{
	const int maxn=1e6+10;

	map<pair<int,int>,bool> win;

	inline void merge(vector<int> &vec,int k){
		int sz=vec.size(),cnt,idx=0,rest,step=k-1,s;
		s=sz/k; cnt=sz%k;
		while(cnt%(k-1)!=0){
			s--; cnt+=k;
		}
		rest=cnt/(k-1);
		vector<int> a,b,c,t;
		if(k==3){
			step=4; rest=1;
		}
		if(k==6){
			s=3471; step=7; rest=1;
		}
		if(k==19){
			s=178; step=18; rest=5;
		}
		for(int i=k-1,j=0,ps=1;i<sz && ps<=s;i+=k,ps++){
			for(int l=j;l<=i;l++)
				for(int r=l+1;r<=i;r++){
					a.push_back(vec[l]);
					b.push_back(vec[r]);
				}
			j=i+1;
		}
		int lst=k*(s-1)+(k-1)+1;
		for(int i=lst+step-1,j=lst,ps=1;i<sz && ps<=rest;i+=step,ps++){
			for(int l=j;l<=i;l++)
				for(int r=l+1;r<=i;r++){
					a.push_back(vec[l]);
					b.push_back(vec[r]);
				}
			j=i+1;
		}
		c=ask(a,b);
		win.clear();
		for(int i=0;i<a.size();i++){
			int x=a[i],y=b[i],z=c[i];
			if(z==x) win[{x,y}]=true;
			else win[{y,x}]=true;
		}
		for(int i=k-1,j=0,ps=1;i<sz && ps<=s;i+=k,ps++){
			for(int l=j;l<=i;l++)
				for(int r=l+1;r<=i;r++)
					if(win[{vec[l],vec[r]}]==true) swap(vec[l],vec[r]); 
			t.push_back(vec[i]);
			j=i+1;
		}
		for(int i=lst+step-1,j=lst,ps=1;i<sz && ps<=rest;i+=step,ps++){
			for(int l=j;l<=i;l++)
				for(int r=l+1;r<=i;r++)
					if(win[{vec[l],vec[r]}]==true) swap(vec[l],vec[r]); 
			t.push_back(vec[i]);
			j=i+1;
		}
		vec.swap(t);
	}

	inline int sol(int n){
		vector<int> vec;
		for(int i=0;i<n;i++) vec.push_back(i);
		for(int i=4;i--;) merge(vec,2);
		merge(vec,3); merge(vec,6); merge(vec,19); 
		merge(vec,183);
		return vec.back();
	}
}

int richest(int N, int T, int S) {
	if(N<=1000) return sub1::sol(N);
	else return sub2::sol(N);
}