#include"souvenirs.h"
#include<bits/stdc++.h>
using namespace std;
stack< pair< vector<int>,long long > > st;
long long F[105],C[105];
void buy_souvenirs(int N,long long P0)
{
vector<int> vi(N);
vi[0]=1;
st.push({vi,P0});
while(!st.empty())
{
vector<int> res=st.top().first;
long long val=st.top().second;
for(int i=0;i<N;i++) if(F[i]&&res[i]) val-=F[i],res[i]=0;
int cnt=0;
for(auto v:res) cnt+=v;
if(!cnt) st.pop();
else if(cnt==1)
{
int pos=0;
for(int i=0;i<N;i++) if(res[i]) F[i]=val,pos=i;
st.pop();
if(pos<N-1&&!F[pos+1])
{
pair< vector<int>,long long > f=transaction(val-1);
vector<int> z(N);
for(auto v:f.first) z[v]=1,C[v]++;
st.push({z,val-1-f.second});
}
}
else
{
long long g=(val-cnt*(cnt+1)/2+cnt-1)/cnt+cnt;
pair< vector<int>,long long > f=transaction(g-1);
vector<int> z(N);
for(auto v:f.first) z[v]=1,C[v]++;
st.push({z,g-1-f.second});
}
}
for(int i=0;i<N;i++) while(C[i]<i) C[i]++,transaction(F[i]);
}
