#include "richest.h"
#include <bits/stdc++.h>
using namespace std;
int len[8]={500000,250000,125000,62500,20833,3472,183,1};
bool vis[1000005];
vector<int>lft,a,b,res,lin;
int richest(int N,int T,int S){
	lft.resize(N);
	for(int i=0;i<=N;i++){
		lft[i]=i;
	}
	for(int o=0;o<8;o++){
		vector<int>().swap(a);
		vector<int>().swap(b);
		int q=N/len[o],r=N%len[o];
		int pos=0;
		for(int i=1;i<=len[o]-r;i++,pos+=q){
			for(int j=pos;j<pos+q;j++){
				for(int k=pos;k<j;k++){
					a.push_back(lft[j]);
					b.push_back(lft[k]);
				} 
			}
		}
		for(int i=1;i<=r;i++,pos+=q+1){
			for(int j=pos;j<pos+q+1;j++){
				for(int k=pos;k<j;k++){
					a.push_back(lft[j]);
					b.push_back(lft[k]);
				}
			}
		}
		res=ask(a,b);
		for(int i=0;i<a.size();i++){
			if(res[i]==a[i])
				vis[b[i]]=1;
			else
				vis[a[i]]=1;
		}
		for(int x:lft){
			if(!vis[x])
				lin.push_back(x);
		}
		lft=lin;
		vector<int>().swap(lin);
		N=lft.size();
		memset(vis,0,sizeof vis);
	}
	return lft[0];
}
//Skadi_H