#include "bits/stdc++.h"
#include "souvenirs.h"
using namespace std;
int N;
vector<long long> cnt_bought, prices;
void find_prices(long long p){
auto [L, R] = transaction(p-1);
for (int x : L)
cnt_bought[x]++;
while (L.size() > 1){
if (prices[L.back()]){
R += prices[L.back()];
L.pop_back();
continue;
}
long long m = (p - 1 - R) / (long long)L.size();
find_prices(m+1);
}
prices[L[0]] = p - 1 - R;
if (L[0] != N-1 && prices[L[0]+1] == 0){
find_prices(prices[L[0]]);
}
}
void buy_souvenirs(int N, long long P0) {
::N = N;
cnt_bought.assign(N, 0);
prices.assign(N, 0);
find_prices(P0);
for (int i = 1; i < N; i++){
while (cnt_bought[i] != i){
transaction(prices[i]);
cnt_bought[i]++;
}
}
}
