#include "richest.h"
#include<bits/stdc++.h>
using namespace std;

int zlicz[1000010];
int na_raz(vector<int>X){
	if(X.size()==1)return X[0];
	vector<int>a,b;
	for(int i=0;i<(int)X.size();i++)
		for(int j=i+1;j<(int)X.size();j++){
			a.push_back(X[i]);
			b.push_back(X[j]);
		}
	vector<int>wynik = ask(a,b);
	for(auto j: wynik)zlicz[j]=0;
	for(auto j: wynik)zlicz[j]++;
	for(auto j: wynik)
		if(zlicz[j]==(int)X.size()-1)return j;
	return 0;
}


map<pair<int,int>, long long>mapa;
map<pair<int,int>, int>strzalka;


long long policz(int n, int t){
	if(mapa[{n, t}]!=0 || n==1)return mapa[{n, t}];
	//printf("%d %d\n", n, t);
	if(t==0)return 1000000000000;
	mapa[{n,t}] = 1000000000000;
	for(long long i=2;i<=n;i++){
		long long pom = ((long long)n/i)*((i*(i-1))/2)+((long long)n%i)*(n%i-1)/2;
		if(mapa[{n,t}]>(long long)policz((n+i-1)/i, t-1)+pom){
			strzalka[{n,t}] = i;
			mapa[{n,t}] = policz((n+i-1)/i, t-1)+pom;
		}
	}
	return mapa[{n,t}];
}
//1099947
//2 2 2 2 3 6 19 182 
//500000 250000 125000 62500 20833 3472 1
vector<int>podzial = {2, 2, 2, 2, 3, 6, 19, 182};
vector<int>podzial2 = {500000, 250000, 125000, 62500, 20833, 3472, 183, 1};
int richest(int n, int t, int s) {
	if(s==2000000)s=1099947;
	//policz(n,t);
	vector<int>mozliwe;
	int i;
	for(i=0;i<n;i++)mozliwe.push_back(i);
	if(t==1){
		return na_raz(mozliwe);
	}
	for(auto pom: podzial2){
//		printf("%d %d\n", pom, n);
		vector<int>a,b;
		vector<vector<int>>podzialy(pom);
		for(i=0;i<(int)mozliwe.size();i++){
			podzialy[i%pom].push_back(mozliwe[i]);
		}
		for(auto j: podzialy){
			for(i=0;i<(int)j.size();i++)
				for(int ij=i+1;ij<(int)j.size();ij++){
					a.push_back(j[i]);
					b.push_back(j[ij]);
				}
		}
		vector<int>wynik = ask(a,b);
		vector<int>nowe;
		for(auto j: mozliwe)zlicz[j]=0;
		for(auto j: wynik)zlicz[j]++;
		for(auto j: podzialy){
			for(auto ij: j){
				if(zlicz[ij]==(int)j.size()-1){
					nowe.push_back(ij);
				}
			}
		}
	s = s-a.size();/*
		if(pom>2){
			
			for(auto j: mozliwe)printf("%d ", j);printf("\n");
			for(auto j: a)printf("%d ", j);printf("\n");
			for(auto j: b)printf("%d ", j);printf("\n");
			for(auto j: nowe)printf("%d ", j);printf("\n");
			printf("   %d %d %d %d\n", n, pom, nowe.size(), (n+pom-1)/pom);
			//return 0;
		}*/
		mozliwe = nowe;
		n = mozliwe.size();
	}
	return mozliwe[0];
	
}