#include <bits/stdc++.h>
#include "souvenirs.h"
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
#define fi first
#define se second
#define vec vector
#define pb push_back
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// typedef long double ld;
// vi cost;
// pair<vi,int> transaction(ll sum){
// vi vs;
// rep(i,sz(cost)){
// if(sum>=cost[i]){
// sum-=cost[i];
// vs.pb(i);
// }
// }
// return {vs,sum};
// }
void buy_souvenirs(int N, long long P0){
int n=N;
ll p0=P0;
p0--;
vec<ll> a(n,-1);
a[0]=p0;
vec<ll> cnt(n);
auto rec=[&](auto self,ll p0)->void{
auto [vs,left]=transaction(p0);
ll sum=p0-left;
for(auto v:vs) cnt[v]+=1;
// print("current sum = ",sum);
// print("indices are");
// for(auto v:vs) cout<<v<<" ";
// print();
int i=vs[0];
if(sz(vs)==1){
a[i]=sum;
}else{
self(self,sum/2);
// rep(j,n) cout<<a[j]<<" ";
// print();
// print(i,vs[1]);
rng(iter,1,sz(vs)) assert(a[vs[iter]]!=-1);
// substract all of the others
rng(iter,1,sz(vs)) sum-=a[vs[iter]];
a[vs[0]]=sum;
}
while(a[i]!=-1) i+=1;
if(i<n){
self(self,a[i-1]-1);
}
};
rec(rec,p0);
rep(i,n){
assert(a[i]>=0);
}
rep(i,n){
rep(_,i-cnt[i]){
transaction(a[i]);
}
}
// rep(i,n){
// cout<<a[i]<<" ";
// }
// print();
// rep(i,n) assert(cnt[i]<=i);
}
// int main(){
// int t;
// cin>>t;
// rep(cs,t){
// // cost={67,37,24,13,8,5};
// // int n=sz(cost);
// int n;
// cin>>n;
// cost=vi(n);
// rep(i,n) cin>>cost[i];
// buy_souvenirs(n,cost[0]);
// // print("~ ~ ~",cs);
// }
// }
