#include <bits/stdc++.h>
using namespace std;
#include "souvenirs.h"
typedef long long ll;
void buy_souvenirs(int N, long long P0) {
vector<ll> cnt(N, 0), val(N, -1);
val[0]=P0;
pair<vector<int>, long long> res;
auto dfs = [&](auto && dfs, vector<int> cur, ll sum)->void{
while(!cur.empty() ){
/*printf("state ");
for(auto it: cur)cout<<it<<", ";
printf(" : sum is %lld\n", sum);
for(auto it: val)cout<<it<<" ";
cout<<endl<<endl;*/
while (!cur.empty() and val[cur.back()] != -1){
sum-=val[cur.back()];
cur.pop_back();
}
if(cur.empty())break;
if(cur.size() == 1){
val[cur.back()]=sum;
if(cur.back() != N-1){
res=transaction(sum-1);
for(auto it: res.first)cnt[it]++;
dfs(dfs, res.first, sum-1-res.second);
}
}
else {
res=transaction(sum/cur.size());
for(auto it: res.first)cnt[it]++;
dfs(dfs, res.first, sum/cur.size() - res.second);
}
}
};
for(int i=1;i<N;i++){
if(val[i] == -1){
res = transaction(val[i-1]-1);
for(auto it : res.first) cnt[it]++;
dfs(dfs, res.first, val[i-1]-1-res.second);
}
}
/*for(auto it:val)cout<<it<<" ";
cout<<endl;*/
for(int i=1;i<N;i++){
assert(cnt[i] <= i);
for(int j=0;j<i-cnt[i];j++) transaction(val[i]);
}
return;
}
