#include "souvenirs.h"
#include <utility>
#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
typedef long long int lld;
int n;
vector<lld> values;
vector<pair<vector<int>,lld > > eqs;
vector<int> tot;
void buy_souvenirs(int N, long long P0) {
n=N;
values.clear();
eqs.clear();
tot.clear();
tot.resize(n,0);
values.resize(n,-1);
vector<int> Frst(n,0);
Frst[0]=1;
eqs.push_back({Frst,P0});
while(true){
sort(eqs.begin(),eqs.end());
bool W=true;
trav(a,values){
if(a==-1)W=false;
}
if(W){
break;
}
int idx=-1;
for(int i=0;i<eqs.size();i++){
bool cl=true;
int pos=n-1-i;
rep(j,0,pos){
if(eqs[i].first[j]!=0)cl=false;
}
if(!cl){
idx=i;
rep(j,pos+1,n){
if(values[j]!=-1 && eqs[i].first[j]==1){
eqs[i].first[j]=0;
eqs[i].second-=values[j];
}
}
break;
}else{
rep(j,pos+1,n){
assert(values[j]!=-1);
if(eqs[i].first[j]==1){
eqs[i].first[j]=0;
eqs[i].second-=values[j];
}
}
values[pos]=eqs[i].second;
}
}
// trav(a,eqs){
// trav(b,a.first){
// cout<<b<<" ";
// }
// cout<<": "<<a.second<<endl;
// }cout<<"==="<<endl;
W=true;
trav(a,values){
if(a==-1)W=false;
}
if(W){
break;
}
int cnt=0;
rep(j,0,n){
cnt+=eqs[idx].first[j];
}
lld val=eqs[idx].second;
if(val%cnt==0){
val=val/cnt-1;
}else{
val=val/cnt;
}
pair<vector<int>,lld> P=transaction(val);
vector<int> row(n,0);
trav(a,P.first)row[a]=1,tot[a]+=1;
eqs.push_back({row,val-P.second});
}
rep(i,1,n){
while(tot[i]<i){
transaction(values[i]);
tot[i]++;
}
}
return;
}
