#include <bits/stdc++.h>
#include "souvenirs.h"
using namespace std;
typedef long long ll;
const int maxn=105;
ll p[maxn],num[maxn],suf;
int cnt[maxn];
vector<int> g[maxn];
void sol(ll v){
auto r=transaction(v);
v-=r.second;
int u=r.first[0];
for(auto x:r.first){
g[u].push_back(x);
cnt[x]++;
}
while(!g[u].empty() && g[u].back()>suf){
v-=num[g[u].back()];
g[u].pop_back();
}
while(suf>u+1){
int k=g[u].size();
ll nv=(v+k-1)/k-1;
sol(nv);
while(!g[u].empty() && suf<=g[u].back()){
v-=num[g[u].back()];
g[u].pop_back();
}
}
num[u]=v;
suf--;
}
void buy_souvenirs(int n, ll p0){
p[0]=p0;
suf=n;
sol(p0-1);
for(int i=1;i<n;i++){
while(cnt[i]<i){
transaction(num[i]);
cnt[i]++;
}
}
}
