#include<bits/stdc++.h>
#include "souvenirs.h"
void buy_souvenirs(int n, long long p0) {
struct basket {
std::vector<int> items = {};
long long s = 0;
};
std::vector<basket> a(n);
std::vector<int> cnt(n);
auto ask = [&](long long s) -> basket {
auto [occ, rem] = transaction(s);
for (auto x : occ) cnt[x]++;
return {occ, s - rem};
};
auto filter = [&](basket& k) -> void {
basket ret;
ret.s = k.s;
for (auto x : k.items) {
if (x == k.items[0] || a[x].items.size() != 1) {
ret.items.push_back(x);
} else {
ret.s -= a[x].s;
}
}
std::swap(ret, k);
};
a[1] = ask(p0 - 1);
for (int i = n - 1; i > 0; --i) {
int j = i;
while (a[j].s == 0) j--;
while (j != i) {
filter(a[j]);
long long q;
if (a[j].items.size() == 1) q = a[j].s - 1;
else q = a[j].s / a[j].items.size();
auto s = ask(q);
j = s.items[0];
a[j] = s;
}
filter(a[i]);
}
for (int i = 0; i < n; ++i) {
while (cnt[i] < i) {
cnt[i]++;
transaction(a[i].s);
}
}
}
