#include "richest.h"
#include<bits/stdc++.h>
using namespace std;
int ix[1000005],nw[1000005],cl,cr;
vector<int> qla,qlb,an;bool v[1000005];
int l[10]={500000,250000,125000,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++){//cout<<i<<" "<<cl<<"\n";
		for(int j=0;j<=1000000;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];
}