#include "richest.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> a,b,c,d;
int cnt[1000005],mp[10]={0,1,183,3472,20833,62500,125000,250000,500000};
void add(int x,int y){
	a.push_back(x),b.push_back(y);
}
void clear(){
	for(int i=0;i<1000000;i++) cnt[i]=0;
}
int richest(int n,int T,int S){
	if(n==1000){
		a.clear(),b.clear(),c.clear();
		for(int i=0;i<n;i++){
			for(int j=i+1;j<n;j++){
				add(i,j);
			}
		}
		c=ask(a,b);
		clear();
		for(int i=0;i<c.size();i++){
			cnt[a[i]+b[i]-c[i]]++; 
		}
		int id=0;
		for(int i=0;i<n;i++){
			if(cnt[i]==0) id=i;
		}
		return id;
	}else{
		clear();
		c.clear();
		for(int i=0;i<n;i++) c.push_back(i);
		for(int ii=8;ii>=1;ii--){
			a.clear(),b.clear(),d.clear();
			int x=n/mp[ii],y=n%mp[ii],pos=0;
	        for(int i=1;i<=mp[ii]-y;i++,pos+=x){
	        	for(int j=pos;j<pos+x;j++){
	        		for(int k=pos;k<j;k++){
	        			add(c[j],c[k]);
					}
				}
			}
	        for(int i=1;i<=y;i++,pos+=x+1){
	        	for(int j=pos;j<=pos+x;j++){
	        		for(int k=pos;k<j;k++){
	        			add(c[j],c[k]);
					}
				}
			}
			d=ask(a,b);
			for(int i=0;i<d.size();i++){
				cnt[a[i]+b[i]-d[i]]++;
			}
			d.clear();
			for(int i:c){
				if(cnt[i]==0) d.push_back(i);
			}
			c=d;
			n=c.size();
			clear();
		}
		return c[0];
	}
	return 1;
}