#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
void buy_souvenirs(int N, long long P0) {
vector<int> bought[N];
long long cst[N];
int cnt[N];
memset(cnt,0,sizeof(cnt));
bought[0] = {0};
cst[0] = P0;
memset(cnt,0,sizeof(cnt));
stack<int> st;
st.push(0);
for(int cur=N;--cur;) {
while(st.top() != cur) {
long long nxt;
if(bought[st.top()].size() == 1)
nxt = cst[st.top()] - 1;
else
nxt = cst[st.top()] / bought[st.top()].size();
auto [nwBuy, nwCst] = transaction(nxt);
for(auto bought: nwBuy)
cnt[bought]++;
nwCst = nxt - nwCst;
while(nwBuy.size() && nwBuy.back() > cur) {
nwCst -= cst[nwBuy.back()];
nwBuy.pop_back();
}
bought[nwBuy[0]] = nwBuy;
cst[nwBuy[0]] = nwCst;
st.push(nwBuy[0]);
}
st.pop();
for(int i=0;i<cur;i++)
if(bought[i].size() && bought[i].back() == cur) {
bought[i].pop_back();
cst[i] -= cst[cur];
}
}
for(int cur=0;cur<N;cur++)
for(int i=cnt[cur];i<cur;i++)
transaction(cst[cur]);
}
