#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
using vi = vector<int>;
using ll = long long;
#define fst first
#define snd second
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
pair<vi, ll> transaction(ll M);
void buy_souvenirs(int N, ll P0) {
vector<ll> total(N);
vector<vi> types(N);
vector<bool> vis(N);
vi need(N);
iota(all(need), 0);
auto query = [&](ll M) {
auto [L, R] = transaction(M);
for (int x : L) need[x]--;
return pair<ll, vi>{M - R, L};
};
total[0] = P0, types[0] = {0}, vis[0] = true;
dforn(i, N) {
int j = i;
while (!vis[j]) j--;
while (true) {
while (types[j].back() > i) {
assert(sz(types[types[j].back()]) == 1);
total[j] -= total[types[j].back()];
types[j].pop_back();
}
if (j == i) break;
assert(j < i);
int C = sz(types[j]);
ll P = C == 1 ? total[j] - 1 : total[j] / C;
auto ret = query(P);
j = ret.snd.front();
tie(total[j], types[j]) = ret, vis[j] = true;
}
}
forn(i, N) while (need[i]) {
query(total[i]);
}
}
