#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
#define I signed
#define int long long
const int INF = 1e18;
void buy_souvenirs(I N, int P0) {
vector<int> cnt(N);
vector<vector<int>> bought(N); // x1: [S, {X}]
vector<int> P(N, 0); P[0] = P0;
int j = -1;
function<void(int,int)> descend = [&](int target, int c) {
pair<vector<I>, int> ret = transaction(c);
int s = c - ret.second;
int x1 = ret.first[0];
bought[x1].push_back(s);
for(int x: ret.first) {
bought[x1].push_back(x);
cnt[x]++;
}
if (x1 == target) return ;
if (ret.first.size() == 1) descend(target, s-1);
else {
if (j != -1 && s/ret.first.size() <= P[j]) return ;
descend(target, s/ret.first.size());
}
};
descend(N-1, P0-1);
P[N-1] = bought[N-1][0];
j = N-1;
while(j > 1) {
int x1;
for(int i = j-1; i >= 1; i--) {
if (bought[i].size()) {
x1 = i;
break;
}
}
if (x1 == j-1) {
int s = bought[x1][0];
for(int k = 2; k < bought[x1].size(); k++) s -= P[bought[x1][k]];
P[x1] = s;
j--;
} else {
int s = bought[x1][0];
while(bought[x1].size() > 2 && P[bought[x1].back()]) {
s -= P[bought[x1].back()];
bought[x1].pop_back();
}
bought[x1][0] = s;
if (bought[x1].size() > 2) descend(j-1, s/(bought[x1].size()-1));
}
}
for(int i = 0; i < N; i++) {
while(cnt[i] < i) {transaction(P[i]); cnt[i]++;}
}
}
