#include <bits/stdc++.h>
#include "souvenirs.h"
using namespace std;
using ll = long long;
vector<int> tr;
vector<ll> vl;
int n;
int solve(int r, ll k) {
auto [vec, sm] = transaction(k);
sm = k - sm;
for (auto i : vec) tr[i]--;
int f = 1;
for (int i = 1; i < vec.size(); i++) f &= vl[vec[i]] != -1;
int i = vec[0];
if (f) {
vl[i] = sm;
for (int j : vec) if (j != i) vl[i] -= vl[j];
if (i == r - 1) return i;
solve(r, vl[i] - 1);
} else {
/*int ln = 1;
for (int i = 1; i < vec.size(); i++) {
if (vec[i] != vec[i - 1] + 1) break;
ln++;
}*/
while (vec.size()) {
if (vec.back() < r) break;
int j = vec.back();
vec.pop_back();
sm -= vl[j];
}
while (vec.size() > 1) {
ll nk = sm / vec.size();
r = solve(r, nk);
while (vec.size()) {
if (vec.back() < r) break;
int j = vec.back();
vec.pop_back();
sm -= vl[j];
}
}
vl[i] = sm;
if (i + 1 < r) {
solve(r, vl[i] - 1);
}
}
return i;
}
void buy_souvenirs(int N, ll P0) {
n = N;
tr.resize(N);
vl.assign(N, -1);
for (int i = 0; i < n; i++) tr[i] = i;
vl[0] = P0;
solve(n, P0 - 1);
for (int i = 0; i < n; i++) for (; tr[i] > 0; tr[i]--) transaction(vl[i]);
}
