/*
______ _____ _______ _ _ _______ __ _ _____ _ _ _
|_____/ | | | |____/ |______ | \ | | | | | |
| \_ |_____| |_____ | \_ ______| | \_| |_____| |__|__|
. . . . . .
_\/ \/_ _\/ \/_ _\/ \/_
_\/\/_ _\/\/_ _\/\/_
_\_\_\/\/_/_/_ _\_\_\/\/_/_/_ _\_\_\/\/_/_/_
/ /_/\/\_\ \ / /_/\/\_\ \ / /_/\/\_\ \
_/\/\_ _/\/\_ _/\/\_
/\ /\ /\ /\ /\ /\
' ' ' ' ' '
*/
//#pragma GCC optimize("Ofast", "unroll-loops")
#include "bits/stdc++.h"
//#pragma GCC target("avx2")
//#pragma GCC target("lzcnt,popcnt")
using namespace std;
using ll = long long;
using bint = __int128;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)x.size()
#define ff first
#define ss second
#define rep(i, a, b) for (int i=a; i<(b); ++i)
#define rev(i, a, b) for (int i=b-1; i>=(a); --i)
template <class Fun>
class y_combinator_result {
Fun fun_;
public:
template <class T>
explicit y_combinator_result(T&& fun)
: fun_(std::forward<T>(fun)) {
}
template <class... Args>
decltype(auto) operator()(Args&&... args) {
return fun_(std::ref(*this), std::forward<Args>(args)...);
}
};
template <class Fun>
decltype(auto) y_combinator(Fun&& fun) {
return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
string yon(ll ans) {
return ans ? "Yes" : "No";
}
template <typename T>
inline void ckmin(T& a, const T b) {
if (a > b)
a = b;
}
template <typename T>
inline void ckmax(T& a, const T b) {
if (a < b)
a = b;
}
inline double get_time() {
return std::chrono::duration_cast<std::chrono::milliseconds>(
std::chrono::system_clock::now().time_since_epoch())
.count();
}
ll popcnt(ll x){return __builtin_popcountll(x);}
ll popcnt_sgn(ll x){return (__builtin_parityll(x)&1 ? -1:1);}
ll topbit(ll x){return (x==0 ? -1:63-__builtin_clzll(x));}
ll lowbit(ll x){return (x==0 ? -1:__builtin_ctzll(x));}
#include "souvenirs.h"
void buy_souvenirs(int n, ll p0) {
vector<int> c(n);
vector<pair<set<int>, ll>> precos(n);
int t=n-1;
vector<int> done(n);
rep(i,0,n) precos[i].ss=-1;
precos[0]={{0}, p0};
done[0]=1;
auto query=[&](ll p) -> auto{
//cout<<">>>"<<p<<endl;
auto q=transaction(p);
for(int u: q.ff) c[u]++;
pair<set<int>, ll> ans={{all(q.ff)}, p-q.ss};
return ans;
};
auto prop=y_combinator([&](auto self, int idx) -> void{
if(done[idx]==0){
done[idx]=1;
t--;
}
rep(i,0,n) if(i!=idx && precos[i].ff.count(idx)){
precos[i].ff.erase(idx);
precos[i].ss-=precos[idx].ss;
if(sz(precos[i].ff)==1) self(i);
}
});
auto cascade=[&](ll cur) -> void{
while(1){
auto q=query(cur);
int y=*q.ff.begin();
precos[y]=q;
if(done[y]) break;
vector<int> rem;
for(int u: precos[y].ff){
if(done[u] && u!=y){
precos[y].ss-=precos[u].ss;
rem.pb(u);
}
}
for(int u: rem) precos[y].ff.erase(u);
if(sz(precos[y].ff)==1){
prop(y);
break;
}else{
cur=q.ss/sz(precos[y].ff);
}
}
};
while(t>0){
//cout<<t<<'\n';
rev(i,1,n){
if(precos[i].ss==-1 && done[i-1]){
cascade(precos[i-1].ss-1);
break;
}
if(sz(precos[i].ff)>1){
cascade(precos[i].ss/sz(precos[i].ff));
break;
}
}
}
rep(i,0,n){
while(c[i]<i){
query(precos[i].ss);
}
}
return;
}
