#include"richest.h"
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define pb push_back
typedef vector<int> vi;
const int N=1e6+3;
int n,tot,val[N];
namespace Sub1
{
	int zc[N];
	int Work()
	{
		vi A,B,C;
		for(int i=0;i<n;i++)zc[i]=0;
		for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)A.pb(i),B.pb(j);
		C=ask(A,B);
		for(int x:C)zc[x]++;
		int s=*max_element(zc,zc+n);
		cerr<<s<<endl;
		return max_element(zc,zc+n)-zc;
	}
};
vi Sol(vi ve,int m)
{
	int i=0,sz=ve.size();vi A,B,C,D,ans;int zz=0;
	for(;i+m<=sz;)
	{
		int st=A.size(),k=m;
		if(sz-i==m+1)k++;
		if(m==19&&++zz<=5)k--;
		for(int x=0;x<k;x++)for(int y=x+1;y<k;y++)A.pb(ve[i+x]),B.pb(ve[i+y]);
		D.pb(A.size()-st);i+=k;
	}
	int st=A.size();
	for(int x=0;x<sz-i;x++)for(int y=x+1;y<sz-i;y++)A.pb(ve[i+x]),B.pb(ve[i+y]);
	if(sz-i)D.pb(A.size()-st);
	C=ask(A,B);tot+=C.size();i=0;
	for(int x:D)
	{
		int mx=0,pos=0;
		for(int j=i;j<i+x;j++)
		{
			val[C[j]]++;
			if(val[C[j]]>mx)mx=val[C[j]],pos=C[j];
		}
		for(int j=i;j<i+x;j++)val[C[j]]=0;
		ans.pb(pos);i+=x;
	}
	return ans;
}
int richest(int _n,int _t,int _s)
{
	tot=0;n=_n;vi ve;
	if(n<=1000)return Sub1::Work();
	for(int i=0;i<n;i++)ve.pb(i);
	ve=Sol(ve,2);
	ve=Sol(ve,2);
	ve=Sol(ve,2);
	ve=Sol(ve,2);
	ve=Sol(ve,3);
	ve=Sol(ve,6);
	ve=Sol(ve,19);
	ve=Sol(ve,ve.size());
	return ve[0];
}