#include <bits/stdc++.h>
using namespace std;
#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<
#define INF (ll)1e18
#define mod 998244353
#define maxn 110
#include "souvenirs.h"
#include <utility>
#include <vector>
void buy_souvenirs(int N, long long P0) {
// full
vector<ll> P(N, -1), rem(N, 0);
iota(rem.begin(), rem.end(), 0);
P[0] = P0;
map<ll, pair<vector<int>, array<ll, 2>>> starts;
auto trans = [&](ll M, bool flag = true) {
auto [v, rem_money] = transaction(M);
/* cerr << "trans" _ M << nf;
for (auto u : v) cerr << u << ' ';
cerr << nf; */
for (auto u : v) rem[u]--;
pair<vector<int>, ll> ans = {v, rem_money};
if (flag) assert(starts.find(v[0]) == starts.end());
starts[v[0]] = {v, {M, rem_money}};
return ans;
};
auto clean = [&](pair<vector<int>, array<ll, 2>> ans) {
auto [v, info] = ans;
vector<int> w;
for (auto u : v) {
if (P[u] != -1) info[1] += P[u];
else w.pb(u);
}
return pair<vector<int>, array<ll, 2>>{w, info};
};
trans(P[0] - 1);
while (true) {
ll mx = -1;
for (ll i = N - 1; i >= 0; i--) {
if (starts.find(i) != starts.end()) {
mx = i; break;
}
}
if (mx == -1) break;
assert(mx != -1);
starts[mx] = clean(starts[mx]);
auto [v, info] = starts[mx];
/* cout << "mx, info =" _ mx _ info[0] - info[1] << nf;
for (auto u : v) cout << u << ' ';
cout << nf; */
if (v.size() == 1) {
starts.erase(mx);
P[mx] = info[0] - info[1];
if (mx != N - 1 && P[mx + 1] == -1) trans(P[mx] - 1);
} else {
trans((info[0] - info[1]) / v.size());
}
}
/* for (ll i = 0; i < N; i++) cerr << P[i] << ' ';
cerr << nf; */
for (ll i = 1; i < N; i++) {
while (rem[i] != 0) {
trans(P[i], false);
}
}
}
