#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void buy_souvenirs(int N, long long P0) {
vector<int> times(N);
vector<pair<vector<int>, ll>> vpv(N, {{}, -1});
vpv[0] = {{}, P0};
auto ask = [&](ll x) {
auto smt = transaction(x);
for (auto a : smt.first)
times[a]++;
vpv[smt.first[0]] = {smt.first, x - smt.second};
vpv[smt.first[0]].first.erase(vpv[smt.first[0]].first.begin());
};
while (1) {
for (int i = 1; i < N; i++) {
if (vpv[i].first.empty() && vpv[i].second == -1 &&
vpv[i - 1].first.empty() && vpv[i - 1].second != -1) {
ask(vpv[i - 1].second - 1);
}
}
for (int i = 0; i < N; i++) {
if (vpv[i].first.empty())
continue;
for (int j = vpv[i].first.size() - 1; j >= 0; j--) {
if (vpv[vpv[i].first[j]].first.empty() &&
vpv[vpv[i].first[j]].second != -1) {
vpv[i].second -= vpv[vpv[i].first[j]].second;
vpv[i].first.erase(vpv[i].first.begin() + j);
}
}
if (vpv[i].first.empty())
continue;
for (int j = i + 1; j <= vpv[i].first.back(); j++) {
if (vpv[j].second != -1) {
goto A;
}
}
ask(vpv[i].second / (vpv[i].first.size() + 1));
A:;
}
for (int i = 0; i < N; i++) {
if (vpv[i].second == -1 || !vpv[i].first.empty()) {
goto B;
}
}
break;
B:;
}
for (int i = 0; i < N; i++) {
while (i != times[i])
ask(vpv[i].second);
}
}
