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