#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<ll> vls;
vector<ll> cn;
ll n;
void gs(ll p0){
auto rs=transaction(p0-1);
rs.second=p0-1-rs.second;
ll ss=rs.second;
ll nn=0;
for(auto thing:rs.first){
if(vls[thing]==-1)nn++;
else ss-=vls[thing];
cn[thing]++;
}
while(nn>=2){
ll na=ss/nn+1;
gs(na);
nn=0;
ss = rs.second;
for(auto thing:rs.first){
if(vls[thing]==-1)nn++;
else ss-=vls[thing];
}
}
for(auto thing:rs.first)if(vls[thing]!=-1)rs.second-=vls[thing];
for(auto thing:rs.first){
if(vls[thing]==-1){
vls[thing]=rs.second;
if(thing!=n-1 && vls[thing+1]==-1)gs(vls[thing]);
}
}
}
void buy_souvenirs(int N, long long P0) {
n=N;
vls.assign(N, -1);
cn.assign(N, 0);
vls[0]=P0;
gs(P0);
for(int i = 0;i<N;i++){
while(cn[i]<i){
transaction(vls[i]);
cn[i]++;
}
}
return;
}
