#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pii pair<int,int>
#define pll pair<long long,long long>
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define pb push_back
#define sz(x) (int)(x).size()
#define rsz resize
#define ass assign
#define F(i,l,r) for(int i=(l);i<(r);++i)
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
template<typename T> using pqg = priority_queue<T, vector<T>, greater<T>>;
#define each(a,x) for(auto a:x)
#define FOR(i,a) for(int i=0;i<(a);i++)
#define ROF(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define eb emplace_back
#define ft front()
#define V vector
#include "souvenirs.h"
void buy_souvenirs(int n,ll p0){
V<ll> p(n);
p[0]=p0;
V<int> bought(n,0);
if(n<=3){
ll m1=p[0]-1;
auto res=transaction(m1);
each(t,res.fi)bought[t]++;
if(n==2)return;
if(n==3){
if(sz(res.fi)==2){
ll sum=m1-res.se,m2=(sum-1)/2;
auto res2=transaction(m2);
each(t,res2.fi)bought[t]++;
p[2]=m2-res2.se;
p[1]=sum-p[2];
}else p[2]=m1-res.se;
}
}else if(p0==(ll)n){
F(i,1,n)p[i]=n-i;
}else{
F(i,1,n){
ll m=p[i-1]-1;
auto res=transaction(m);
each(t,res.fi)bought[t]++;
p[i]=m-res.se;
}
}
F(i,1,n){
if(!p[i])continue;
while(bought[i]<i){
transaction(p[i]);
bought[i]++;
}
}
}
