#include <iostream>
#include <vector>
#include <set>
#define int long long
using namespace std;
struct comp{
bool operator()(pair<set<int32_t>, int> a, pair<set<int32_t>, int> b) const {
return *a.first.begin() > *b.first.begin();
}
};
pair<vector<int32_t>, int> transaction(int m);
pair<set<int32_t>, int> equate(vector<int32_t>& idx, int l, int o, vector<int>& cnt) {
set<int32_t> f;
for (auto x : idx) f.insert(x), ++cnt[x];
return make_pair(f, o - l);
}
void buy_souvenirs(int32_t n, int p0) {
auto r = transaction(p0 - 1);
set<pair<set<int32_t>, int>, comp> s;
vector<int> p(n, -1), cnt(n, 0);
set<int32_t> u;
for (int i = 1; i < n; ++i) u.insert(i);
s.insert(equate(r.first, r.second, p0 - 1, cnt));
while (s.size() && u.size()) {
auto c = *s.begin();
vector<int> rm;
for (auto x : c.first)
if (p[x] != -1)
rm.push_back(x);
for (auto x : rm)
c.first.erase(x),
c.second -= p[x];
if (c.first.size() > 1) {
int nxt = c.second / c.first.size();
r = transaction(nxt);
s.insert(equate(r.first, r.second, nxt, cnt));
}
else {
int idx = *c.first.begin();
u.erase(idx);
p[idx] = c.second;
s.erase(s.begin());
if (!u.size()) break;
if (*u.rbegin() > idx) {
int nxt = c.second - 1;
r = transaction(nxt);
s.insert(equate(r.first, r.second, nxt, cnt));
}
}
}
for (int i = 1; i < n; ++i)
for (int j = cnt[i]; j < i; ++j)
transaction(p[i]);
}
