#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}];
}
vector<int>podzial = {2, 2, 2, 2, 3, 6, 19, 183};
int richest(int n, int t, int s) {
	if(s==2000000)s=1099960;
	//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: podzial){
		//printf("%d %d %d %d\n", pom, s, n, mapa[{s,n}]);
		vector<int>a,b;
		for(i=0;i<(int)mozliwe.size();i++){
			for(int j=i+1;j<(int)mozliwe.size() && j%pom;j++){
				a.push_back(mozliwe[i]);
				b.push_back(mozliwe[j]);
			}
		}
		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: mozliwe)
			if(zlicz[j]==pom-1){
				nowe.push_back(j);
			}
		if(mozliwe.size()%pom){
			int reszta = mozliwe.size()%pom;
			for(int i=mozliwe.size()/pom*pom;i<(int)mozliwe.size();i++)
				if(zlicz[mozliwe[i]]==reszta-1)
					nowe.push_back(mozliwe[i]);
		}
		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];
	
}