#include "souvenirs.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 104;
vector<int> vec,v[N];
ll sum[N];
ll res;
int n,freq[N];
ll p[N];
void my_transaction(ll m){
auto x = transaction(m);
vec = x.first;
res = x.second;
}
void completar(int i){
while (freq[i] < i){
transaction(p[i]);
freq[i]++;
}
}
ll min_val(ll S,int k){
int val = k*(k-1)/2;
S += val + k-1;
return S/k;
}
void go(ll limit){
// cout << "go : " << limit << "\n";
my_transaction(limit);
int pos = *vec.begin();
sum[pos] = limit - res;
v[pos] = vec;
for (int x : vec)
freq[x]++;
while (v[pos].size() > 1){
while (p[v[pos].back()] > 0){
sum[pos] -= p[v[pos].back()];
v[pos].pop_back();
}
int k = v[pos].size();
if (k > 1)
go(min_val(sum[pos], k) - 1);
}
// cout << "sale while " << limit << " -> " << sum[pos] << "\n";
p[pos] = sum[pos];
if (pos+1 < n && p[pos+1] == 0)
go(p[pos] - 1);
// cout << "sale " << limit << "\n";
}
void buy_souvenirs(int N,ll p0){
n = N;
p[0] = p0;
go(p0 - 1);
/*
cout << "p : ";
for (int i=0; i<n; i++)
cout << p[i] << " ";
cout << "\n";
*/
for (int i=1; i<n; i++)
completar(i);
}
