#include "souvenirs.h"
#include <utility>
#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define _ << " " <<
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define ull unsigned long long
#define lll __int128
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define BlueCrowner ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define FORD(i, a, b) for (ll i = (a); i >= (b); i--)
ll cnt[105], price[105], n;
void find_price(ll p) {
auto [v, l] = transaction(p);
FOR(i, 0, v.size()) cnt[v[i]]++;
while(v.size() > 1) {
if(price[v.back()] > 0) {
l += price[v.back()];
v.pop_back();
}
find_price((p - l) / v.size());
}
price[v[0]] = p - l;
if(price[v[0] + 1] == 0 && v[0] != n - 1) find_price(price[v[0]] - 1);
}
void buy_souvenirs(int N, ll p0) {
n = N;
find_price(p0 - 1);
FOR(i, 1, n) while(cnt[i] < i) transaction(price[i]), cnt[i]++;
}
