#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;
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 descend(target, s/ret.first.size());
};
descend(N-1, P0-1);
P[N-1] = bought[N-1][0];
for(int j = N-1; j > 1; j--) {
int x1;
for(int i = j-1; i >= 1; i--) if (bought[i].size()) {x1 = i; break;}
vector<int> &v = bought[x1];
if (x1 == j-1) {
int s = v[0];
for(int k = 1; k < v.size()-1; k++) s -= P[v[1+k]];
P[x1] = s;
} else {
int s = v[0];
while(v.size() > 1 && P[v.back()]) {
s -= P[v.back()];
v.pop_back();
}
descend(j-1, s/(v.size()-1));
for(int k = 1; k < bought[x1].size()-1; k++) {
s -= P[bought[x1][1+k]];
}
P[x1] = s;
}
}
for(int i = 0; i < N; i++) {
while(cnt[i] < i) {transaction(P[i]); cnt[i]++;}
}
}
