#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=150,inf=1e9;
const ll INF=1e18;
int num[N],n;
ll val[N];
vector<pair<vector<int>,ll>>Qs;
ll Ask(ll x){
//printf("%i\n",x);
pair<vector<int>,ll>y=transaction(x);
//int temp[n+10]={0};
//for(auto i:y.fi)temp[i]=1;
//for(int i=0;i<n;i++) printf("%i ",temp[i]);printf("\n");
Qs.pb({y.fi,x-y.se});
for(auto i:y.fi)num[i]++;
return Qs.back().se;
}
ll Sum(int j){
ll x=Qs[j].se;
for(auto i:Qs[j].fi)if(val[i])x-=val[i];
return x;
}
int Cnt(int j){
int x=Qs[j].fi.size();
for(auto i:Qs[j].fi)if(val[i])x--;
return x;
}
int Mx(int j){
int mx=0;
for(auto i:Qs[j].fi)if(!val[i])mx=max(mx,i);
return mx;
}
void Clear(){
Qs.clear();
for(int i=0;i<=n;i++)num[i]=val[i]=0;
n=0;
}
void buy_souvenirs(int n1,ll P0){
n=n1;
Ask(P0-1);
for(int I=n-1;I>=1;I--){
//printf("* %i\n",I);
ll mn=INF;int j=0;
for(int i=0;i<Qs.size();i++)if(Cnt(i)!=0){
ll x=Sum(i)/Cnt(i)-1;
if(Mx(i)==I)x++;
//printf("{%i %lld}\n",i,x);
if(mn>x||(mn==x&&Cnt(i)<Cnt(j)))mn=x,j=i;
}
//printf("%i\n",j);
while(!(Cnt(j)==1&&Mx(j)==I)){
ll x=Sum(j)/Cnt(j)-1;
if(Mx(j)==I)x++;
Ask(x);
j=Qs.size()-1;
}
val[I]=Sum(j);
}
//printf("dopuna\n");
for(int i=1;i<n;i++){
while(num[i]<i)Ask(val[i]);
}
Clear();
}
