#include "souvenirs.h"
#include <utility>
#include <vector>
#include <iostream>
using namespace std;
using ll = long long;
void a(int l, int r);
void b(int l, int r, vector<int>& v, ll sum);
ll p[100], cnt[100];
void buy_souvenirs(int N, long long P0) {
p[0] = P0;
a(1, N);
for (int i = 0; i < N; i++) {
// cout << p[i] << ' ';
for (int j = 0; j < i-cnt[i]; j++) transaction(p[i]);
}
}
void a(int l, int r) {
if (l == r) return;
if (l == r-1) {
ll u = p[l-1]-1;
pair<vector<int>, ll> v = transaction(u);
for (auto e: v.first) cnt[e]++;
for (auto e: v.first) if (e >= r) u -= p[e];
for (auto e: v.first) if (e >= r) v.first.erase(lower_bound(v.first.begin(), v.first.end(), e));
p[l] = u - v.second;
return;
}
ll u = p[l-1]-1;
pair<vector<int>, ll> v = transaction(u);
for (auto e: v.first) cnt[e]++;
for (auto e: v.first) if (e >= r) u -= p[e];
for (auto e: v.first) if (e >= r) v.first.erase(lower_bound(v.first.begin(), v.first.end(), e));
if (v.first.size() == 1) p[v.first[0]] = u-v.second;
b(l, v.first.back()+1, v.first, u-v.second);
a(v.first.back()+1, r);
}
void b(int l, int r, vector<int>& v, ll sum) {
if (l == r || v.empty()) return;
if (l == r-1) {
for (auto e: v) if (e >= r) sum -= p[e];
for (auto e: v) if (e >= r) v.erase(lower_bound(v.begin(), v.end(), e));
p[v[0]] = sum;
return;
}
ll L = 0, R = sum, mid, u;
while (L < R) {
mid = (L + R) >> 1;
ll check = 0;
for (auto e: v) check += mid + (l-e);
if (check >= sum) R = mid - 1;
else L = mid + 1, u = mid;
}
pair<vector<int>, ll> w = transaction(u);
for (auto e: w.first) cnt[e]++;
for (auto e: w.first) if (e >= r) u -= p[e];
for (auto e: w.first) if (e >= r) w.first.erase(lower_bound(w.first.begin(), w.first.end(), e));
if (w.first.size() == 1) p[w.first[0]] = u-w.second;
b(w.first[0], w.first.back()+1, w.first, u-w.second);
a(w.first.back()+1, r);
vector<int> k;
for (auto e: v) if (e >= l) sum -= p[e];
for (auto e: v) if (e < w.first[0]) k.push_back(e);
b(l, w.first[0], k, sum);
}
