#pragma GCC optimize("Ofast,unroll-loops,inline,fast-math,omit-frame-pointer")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt,tune=native,fma")
#include <bits/stdc++.h>
#include "souvenirs.h"
#define ll long long
#define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0)
using namespace std;
vector<ll>p;
vector<int>b;
int N,ft;
void buy_souvenirs(int n, ll P0) {
queue<pair<int,ll>>q;
N=n,p.assign(N,-1),b.assign(N,0),p[0]=P0,q.push({1,P0});
while(q.size()) {
auto[idx,up]=q.front();q.pop();
if(idx>=N||p[idx]^-1)continue;
auto[it,ch]=transaction(up-1);
for(int t:it)b[t]++;
vector<int>pd;
ll lo=ch;
for(int i=it.size()-1,t;i;i--)t=it[i],p[t]^-1?pd.push_back(t),0:lo+=p[t];
if(pd.size()) {
ll rm=up-1-lo,av=rm/(pd.size()+1)+1;
for(int t:pd)q.push({t,av});
q.push({idx,up});
continue;
}
ft=it[0],p[ft]=up-1-lo,q.push({ft+1,p[ft]});
}
for(int i=1;i<N;i++) {
while(b[i]<i) {
auto[it,ch]=transaction(p[i]);
for(int t:it)b[t]++;
}
}
}
