#include "souvenirs.h"
#include <utility>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fs first
#define sc second
void buy_souvenirs(int n, long long p0) {
vector<int> vr;
ll rr;
int a[n];
memset(a,0,sizeof(a));
ll p[n];
memset(p,0,sizeof(p));
p[0]=p0;
pair<vector<int>,ll> rs,tt[n];
vector<int> id={0};
ll x=p0;
while(id[0]!=n-1){
if(id.size()==1)x--;
else x/=2;
rs=transaction(x);
id=rs.fs,x-=rs.sc;
for(int i:id){
a[i]++;
if(i!=id[0])tt[id[0]].fs.push_back(i);
}
tt[id[0]].sc=x;
}
// for(int i=0;i<n;i++)if(tt[i].sc){
// cout<<i<<": ";
// for(int j:tt[i].fs)cout<<j<<' ';
// cout<<"| "<<tt[i].sc<<'\n';
// }
for(int i=n-1;i;i--){
if(tt[i].sc){
p[i]=tt[i].sc;
for(int j:tt[i].fs)p[i]-=p[j];
}else{
assert(0);
// rs=transaction(p[i+1]*2);
// vr=rs.fs,rr=rs.sc;
}
}
// for(ll i:p)cout<<i<<' ';
// cout<<'\n';
for(int i=1;i<n;i++){
for(;a[i]<i;a[i]++){
transaction(p[i]);
}
}
}
