#include "richest.h"
#include<bits/stdc++.h>
using namespace std;
const int V=1e6+1;
int ix[V],nw[V],cl,cr;
vector<int> qla,qlb,an;bool v[V];
int l[10]={V/2,V/4,V/8,62496,20832,3472,183,1};

int richest(int N, int T, int S) {
	cl=N;for(int i=1;i<=N;i++)ix[i]=i-1,nw[i]=0,v[i]=0;cr=0;
	for(int i=(N==1000?7:0);i<8;i++){
		for(int j=0;j<V;j++)v[i]=0;qla.clear();qlb.clear(); 
		for(int j=l[i]+1;j<=cl;j++)
			for(int k=j-l[i];k>0;k-=l[i])
				qla.push_back(ix[k]),qlb.push_back(ix[j]);
		an=ask(qla,qlb);cr=0;
		for(int j=l[i]+1;j<=cl;j++)
			for(int k=j-l[i];k>0;k-=l[i])
				v[ix[j]+ix[k]-an[cr++]]=1;
		cr=0;for(int j=1;j<=cl;j++)if(!v[ix[j]])nw[++cr]=ix[j];
		for(int j=1;j<=cr;j++)ix[j]=nw[j];cl=cr;
	}return ix[1];
}