#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define bl ' '
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define comp(v) (v).erase(unique(all(v)), (v).end())
#define lbd(v,x) lower_bound(all(v), (x))-(v).begin()
#define ubd(v,x) upper_bound(all(v), (x))-(v).begin()
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<int, pi> ipi;
typedef pair<pi, pi> pipi;
typedef pair<ll, ll> pll;
const int MAXN = 100100*1;
const ll MOD = 1e9+7;
const ll INF = 1e9+10;
pair<vector<int>, ll> res;
int cnt[110];
ll arr[110];
void dnc(int s, int e, ll tot) {
ll sum = tot - res.ss;
auto v = res.ff; int sz = v.size();
if(s == e) {
arr[s] = sum;
return;
}
if(sz == 1) {
arr[s] = sum;
res = transaction(sum-1);
for(int x:res.ff) cnt[x]++;
dnc(s+1, e, sum-1);
return;
}
ll avg = sum/sz;
res = transaction(avg);
for(int x:res.ff) cnt[x]++;
int idx = res.ff[0];
dnc(idx, e, avg);
while(v.size() && v.back() >= idx) {
sum -= arr[v.back()]; v.pop_back();
}
res = make_pair(v, 0);
dnc(s, idx-1, sum);
}
void buy_souvenirs(int N, ll P0) {
res = transaction(P0-1);
for(int x:res.ff) cnt[x]++;
dnc(1, N-1, P0-1);
for(int i=1; i<N; i++) {
while(cnt[i] < i) {
transaction(arr[i]);
cnt[i]++;
}
}
}
