#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 s, int n){
	if(mapa[{s,n}]!=0)return mapa[{s,n}];
	mapa[{s,n}] = 1000000000000;
	if((long long)n*(n-1)/2<=s){
		mapa[{s,n}] = 1;
		strzalka[{s,n}] = n;
		return 1;
	}
	for(long long i=1;i<=5;i++){
		long long pom = ((long long)n/i)*((i*(i-1))/2)+((long long)n%i)*(n%i-1)/2;
		if(pom>s)continue;
		if(mapa[{s,n}]>policz(s-pom, (n+i-1)/i)+1){
			strzalka[{s,n}] = i;
			mapa[{s,n}] = policz(s-pom, (n+i-1)/i)+1;
		}
	}
	return mapa[{s,n}];
}
int richest(int n, int t, int s) {
	if(s==2000000)s=1099973;
	policz(s,n);
	vector<int>mozliwe;
	int i;
	for(i=0;i<n;i++)mozliwe.push_back(i);
	while(strzalka[{s,n}]!=n){
		int pom = strzalka[{s,n}];
//		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 na_raz(mozliwe);
	
}