#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;
}

int richest(int n, int t, int s) {
	if(s==2000000)s=1099944;
	vector<int>mozliwe;
	int i;
	for(i=0;i<n;i++)mozliwe.push_back(i);
	while(!((long long)mozliwe.size()*((long long)mozliwe.size()-1)/2<=(long long)s)){
		if(((long long)mozliwe.size()*((long long)mozliwe.size()-1)/2<=(long long)s+100000))break;
//		printf("srodek %lld %d\n", (long long)mozliwe.size()*((long long)mozliwe.size()-1)/2, s);
//	while(mozliwe.size()>1){
		vector<int>a,b;
		for(i=0;i<(int)mozliwe.size();i++){
			if(i%2==1)b.push_back(mozliwe[i]);
			if(i%2==0 && i!=(int)mozliwe.size()-1)a.push_back(mozliwe[i]);
		}
		if(!mozliwe.size()%2)
			mozliwe = ask(a,b);
		else{
			int pom = mozliwe.back();
			mozliwe = ask(a,b);
			mozliwe.push_back(pom);
		}
		s-=a.size();
	}
	while(((long long)mozliwe.size()*((long long)mozliwe.size()-1)/2>(long long)s))mozliwe.pop_back();
//	return mozliwe[0];
	return na_raz (mozliwe);
	
}