#include<bits/stdc++.h>
 #include "richest.h"
#define pb emplace_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int maxn=1e6+10;
typedef long long ll;
void chkmax(int &x,int y){ x=x>y?x:y; }
void chkmin(int &x,int y){ x=x<y?x:y; }
vector<int> ask(vector<int> a,vector<int> b);
int len[8]={500000,250000,125000,62500,20833,3472,183,1},vis[maxn];
vector<int> a,b,res,p;
void solve(vector<int> p){
	for(auto u:p)
		for(auto v:p){
			if(u>=v) continue;
			a.pb(u); b.pb(v);
		}
}
int richest(int N,int T,int S){
	p.clear(); for(int i=0;i<N;i++) p.pb(i);
	if(T==20){
		vector<int> tmp;
		for(int i=0;i<8;i++){
			tmp.clear(); a.clear(); b.clear();
			for(int j=0;j<p.size();j++)
				for(int k=j%len[i];k<j;k+=len[i]) a.pb(p[k]),b.pb(p[j]);
			res=ask(a,b);
			for(auto z:p) vis[z]=1;
			for(int i=0;i<a.size();i++)
				if(res[i]==a[i]) vis[b[i]]=0;
				else vis[a[i]]=0;
			for(auto z:p)
				if(vis[z]) tmp.pb(z),vis[z]=0;
			swap(p,tmp);
		}
		return p[0];
	}else{
		a.clear(); b.clear();
		solve(p); int ans;
		res=ask(a,b);
		for(auto z:p) vis[z]=1;
		for(int i=0;i<a.size();i++)
			if(res[i]==a[i]) vis[b[i]]=0;
			else vis[a[i]]=0;
		for(auto z:p)
			if(vis[z]) ans=z,vis[z]=0;;
		return ans;
	}
}