#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
#define I signed
#define int long long
void buy_souvenirs(I N, int P0) {
vector<int> cnt(N);
struct eqn {
int s;
vector<int> v; // x1 .. xk
};
vector<eqn> E(N); // bought[x1]
vector<int> P(N, 0); P[0] = P0;
function<void(int,int)> descend = [&](int target, int c) {
pair<vector<I>, int> ret = transaction(c);
int x1 = ret.first[0];
E[x1].s = c - ret.second;
for(int x: ret.first) {
if (P[x]) E[x1].s -= P[x];
else E[x1].v.push_back(x);
cnt[x]++;
}
if (x1 == target) return ;
if (E[x1].v.size() == 1) descend(target, E[x1].s-1);
else descend(target, E[x1].s/E[x1].v.size());
};
descend(N-1, P[0]-1);
P[N-1] = E[N-1].s;
int j = N-1;
while(j > 1) {
int x1;
for(int i = j-1; i >= 1; i--) {
if (E[i].v.size() && !P[i]) {
x1 = i;
break;
}
}
if (x1 == j-1) {
while(E[x1].v.size() > 1) {
E[x1].s -= P[E[x1].v.back()];
E[x1].v.pop_back();
}
P[x1] = E[x1].s;
j--;
} else {
while(E[x1].v.size() > 1 && P[E[x1].v.back()]) {
E[x1].s -= P[E[x1].v.back()];
E[x1].v.pop_back();
}
if (E[x1].v.size() == 1) {
P[x1] = E[x1].s;
descend(j-1, P[x1]-1);
}
else descend(j-1, E[x1].s/(E[x1].v.size()));
}
}
for(int i = 0; i < N; i++) {
while(cnt[i] < i) {transaction(P[i]); cnt[i]++;}
}
}
