#include"richest.h"
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
#define inf 1000000000
#define infll 1000000000000000000ll
#define pii pair<int,int>
#define rep(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define per(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define F(i,a,b) for(int i=(a);i<=(b);i++)
#define dF(i,a,b) for(int i=(a);i>=(b);i--)
#define cmh(sjy) while(sjy--)
#define lowbit(x) (x&(-x))
#define HH printf("\n")
#define eb emplace_back
#define poly vector<int>
using namespace std;
const int maxn=1000005;
int cnt[maxn];
int getmax(vector<int>vec){
	vector<int>A,B;
	int siz=vec.size();
	if(siz==1)return vec[0];
	F(i,0,siz-2)F(j,i+1,siz-1)A.push_back(vec[i]),B.push_back(vec[j]);
	vector<int>res=ask(A,B);
	for(int i:res)++cnt[i];
	int rt=0;
	for(int i:vec)if(cnt[i]==siz-1)rt=i;
	for(int i:res)--cnt[i];
	return rt;
}
vector<int>qa,qb;
array<int,3>pushquery(vector<int>vec){
	const int siz=vec.size(),l=qa.size();
	F(i,0,siz-2)F(j,i+1,siz-1)qa.push_back(vec[i]),qb.push_back(vec[j]);
	const int r=qa.size()-1;
	return {l,r,siz};
}
vector<int>getnxt(vector<int>vec,int nxt){
	qa.clear(),qb.clear();
	const int n=vec.size();
	vector<int>res;
	const int p=n/nxt,p1=p+1,q=(nxt-n%nxt),q1=n%nxt;
	int c0=0,c1=0,ord=0,st=0;
	vector<int>qu;
	vector<array<int,5>>qwq;
	F(i,0,n-1){
		++ord,qu.push_back(vec[i]);
		if(ord==p&&c0<q){
			array<int,3>tmp=pushquery(qu);
			++c0,ord=0,qwq.push_back({tmp[0],tmp[1],tmp[2],st,i});
			qu.clear();
			st=i+1;
		}
		if(ord==p1&&c1<q1){
			array<int,3>tmp=pushquery(qu);
			++c1,ord=0,qwq.push_back({tmp[0],tmp[1],tmp[2],st,i});
			qu.clear();
			st=i+1;
		}
	}
	vector<int>qres=ask(qa,qb);
	for(auto [l,r,siz,st,ed]:qwq){
		F(i,l,r)++cnt[qres[i]];
		F(i,st,ed)if(cnt[vec[i]]==siz-1)res.push_back(vec[i]);
		F(i,l,r)--cnt[qres[i]];
	}
	return res;
}
int richest(int N, int T, int S){
	vector<int>vec;
	F(i,0,N-1)vec.push_back(i);
	if(N==1000)return getmax(vec);
	vec=getnxt(vec,500000);
	vec=getnxt(vec,250000);
	vec=getnxt(vec,125000);
	vec=getnxt(vec,62500);
	vec=getnxt(vec,20833);
	vec=getnxt(vec,3472);
	vec=getnxt(vec,183);
	return getmax(vec);
}