#include "souvenirs.h"
#include <bits/stdc++.h>
#define ll long long
#define dbg(x) cerr<<#x << ' ' << x << endl;
using namespace std;
ll n;
vector<ll> value;
vector<ll> cnt;
void printvec(vector<ll>& v)
{
for (auto &&e : v)
{
cout << e << ' ' ;
}
cout << endl;
}
void gad(vector<int>& v)
{
for (auto &&e : v)
{
cnt[e]++;
}
}
void buy_souvenirs(int N, long long P0) {
// std::pair<std::vector<int>, long long> res = transaction(3);
n=N;
value.resize(n);
cnt.resize(n);
value[0]=P0;
ll j=0;
while(j<n-1)
{
ll val=value[j]/2;
if(j==n-2) val=value[j]-1;
if(val<0) cout<<"nooo"<<endl;
pair<vector<int>,ll> res = transaction(val);
gad(res.first);
j=res.first[0];
value[j]=val-res.second;
}
for (int i=n-1;i>=0;i--)
{
if(value[i]==0)
{
if(value[i-1]==0)cout <<"noooo"<<endl;
pair<vector<int>,ll> res = transaction(value[i-1]-1);
ll val=value[i-1]-1-res.second;
for (auto &&e : res.first)
{
if(e!=i)val-=value[e];
}
value[i]=val;
gad(res.first);
}
}
for (int i=1;i<n;i++)
{
while(cnt[i]<i)
{
pair<vector<int>,ll> res = transaction(value[i]);
cnt[i]++;
}
}
return;
}
