#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;
map<ll,pair<ll,ll>> mp;
pair<vector<int>,ll> res1 = transaction(P0-1);
gad(res1.first);
mp[1]={P0-1-res1.second,res1.first.size()};
if(res1.first.size()==1)
{
value[1]=P0-1-res1.second;
}
for (int i=n-1;i>=1;i--)
{
if(value[i]==0)
{
ll val=0;
for (int j=i;j>=0;j--)
{
if(mp[j].first!=0)
{
val=mp[j].first/mp[j].second;
if(mp[j].second==1)
{
val=mp[j].first-1;
}
break;
}
}
while(value[i]==0)
{
pair<vector<int>,ll> res = transaction(val);
vector<ll> v;
ll sm=val-res.second;
for (auto &&e : res.first)
{
sm-=value[e];
if(value[e]==0)
{
v.push_back(e);
}
}
mp[v[0]]={sm,v.size()};
if(v.size()==1)
{
value[v[0]]=sm;
}
gad(res.first);
val=sm/v.size();
if(v.size()==1)
{
val=sm-1;
}
}
}
}
for (int i=1;i<n;i++)
{
while(cnt[i]<i)
{
pair<vector<int>,ll> res = transaction(value[i]);
cnt[i]++;
}
}
return;
}
