#include "souvenirs.h"
#include <utility>
#include <vector>
#include <stack>
using namespace std;
void buy_souvenirs(int N, long long P0) {
vector<long long> val(N, -1);
vector<int> cnt(N, 0);
val[0] = P0;
int known = 1;
stack<pair<vector<int>, long long>> s;
while (known < N) {
if (s.size()) {
vector<int> a = s.top().first;
long long sum = s.top().second;
s.pop();
vector<int> b;
for (int &x : a) {
if (val[x] != -1) sum -= val[x];
else b.push_back(x);
}
swap(a, b);
if (a.size() == 1) {
val[a[0]] = sum;
++known;
} else if (a.size() > 1) {
s.push({a, sum});
long long n = a.size();
auto [res, rem] = transaction(sum / n);
for (int &i : res) ++cnt[i];
s.push({res, sum / n - rem});
}
} else {
int i = 0;
for (; i < N; i++) {
if (val[i] == -1) {
i -= 1;
break;
}
}
auto [res, rem] = transaction(val[i] - 1);
for (int &i : res) ++cnt[i];
s.push({res, val[i] - 1 - rem});
}
}
for (int i = 1; i < N; i++) {
while (cnt[i] < i) {
transaction(val[i]);
++cnt[i];
}
}
return;
}
