#include <bits/stdc++.h>
#include "souvenirs.h"
using namespace std;
long long n;
long long cnt[101];
long long cost[101];
void Solve(long long money){
pair<vector<int>, long long> vp1;
vp1= transaction(money);
for (int i=0; i<vp1.first.size(); i++){
cnt[vp1.first[i]]++;
}
while(vp1.first.size()>1){
if(cost[vp1.first.back()]!=-1){
vp1.second+=cost[vp1.first.back()];
vp1.first.pop_back();
}
else{
Solve((money-vp1.second)/vp1.first.size());
}
}
cost[vp1.first[0]]=money-vp1.second;
if(vp1.first[0]!=n-1 && cost[vp1.first[0]+1]==-1){
Solve(cost[vp1.first[0]]-1);
}
}
pair<vector<int>, long long> transaction(long long M);
void buy_souvenirs(int N, long long P0) {
n=N;
pair<vector<int>, long long> vp;
if (n==2){
transaction(P0-1);
}
else if (n==3){
vp=transaction(P0-1);
if (vp.first.size()==1){
long long tt=vp.second;
long long p2=P0-1-tt;
transaction(p2-1);
transaction(p2-1);
}
else{
long long tt=vp.second;
long long p2=(P0-1-tt)/2;
transaction(p2);
}
}
/*
else{
long long sm=n-2;
for (int i=1; i<n; i++){
long long cnt=i-1;
if (i==n-1){
cnt=sm;
}
vp=transaction(P0-1);
long long tt=vp.second;
if (vp.first.size()==2){sm--;tt++;}
long long pk=P0-1-tt;
P0=pk;
for (int j=0; j<cnt; j++){
transaction(pk);
}
}
}
*/
else{
memset(cnt,0,sizeof(cnt));
memset(cost,-1,sizeof(cost));
cost[0]=P0;
Solve(P0-1);
for(int i=1; i<n; i++){
for(int j=i; j>cnt[i]; j--){
transaction(cost[i]);
}
}
}
}
