#include"richest.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>ask(vector<int>a,vector<int>b);
vector<int>get_division(vector<int>v,vector<int>division){
    static int sum,tot,lmax;
    static vector<int>ret,a,b,c;
    static map<pair<int,int>,int>mp;
    ret.clear();
    a.clear(),b.clear(),mp.clear();
    sum=tot=0;
    for(auto p:division){
        for(int i=sum;i<sum+p;i++)
        	for(int j=i+1;j<sum+p;j++)
        		a.push_back(v[i]),b.push_back(v[j]),mp[{v[i],v[j]}]=tot++;
        sum+=p;
    }
    c=ask(a,b);
    sum=0;
    for(auto p:division){
    	lmax=v[sum];
    	for(int i=sum+1;i<sum+p;i++)
    		lmax=c[mp[{lmax,v[i]}]];
    	ret.push_back(lmax);
    	sum+=p;
	}
    return ret;
}
void test(vector<int>k){
    for(auto t:k)
    	cerr<<t<<' ';
    cerr<<'\n';
}
int richest(int n,int t,int s){
    if(n==1000){
        vector<int>v;
        for(int i=0;i<n;i++)
            v.push_back(i);
        return get_division(v,vector<int>(1,1000))[0];
    }
    static vector<int>k,divi;
    k.clear(),divi.clear();
    for(int i=0;i<n;i++)
        k.push_back(i);
    for(int i=0;i<500000;i++)//1
        divi.push_back(2);
    k=get_division(k,divi);
    divi.clear();
    for(int i=0;i<250000;i++)//2
        divi.push_back(2);
    k=get_division(k,divi);
    divi.clear();
    for(int i=0;i<125000;i++)//3
        divi.push_back(2);
    k=get_division(k,divi);
    divi.clear();
    for(int i=0;i<62500;i++)//4
        divi.push_back(2);
    k=get_division(k,divi);
    divi.clear();
    divi.push_back(4);
    for(int i=0;i<20832;i++)//5
        divi.push_back(3);
    k=get_division(k,divi);
    divi.clear();
    divi.push_back(7);
    for(int i=0;i<3471;i++)//6
        divi.push_back(6);
    k=get_division(k,divi);
    divi.clear();
    for(int i=0;i<5;i++)//7
        divi.push_back(18);
    for(int i=0;i<178;i++)
        divi.push_back(19);
    k=get_division(k,divi);
    divi.resize(2);
    divi[0]=182,divi[1]=1;
    return get_division(k,divi)[1];
}