#include <bits/stdc++.h>
#include "souvenirs.h"
using namespace std;
typedef long long i64;
int N;
vector<optional<i64>> costs;
vector<int> buy_count;
struct Purchase {
i64 cost;
vector<int> items;
};
void solve_suffix(int start);
void shorten(Purchase purchase);
Purchase process(Purchase purchase) {
auto [cost, items] = purchase;
for (int i = 0; i < items.size(); i++) {
if (costs[items[i]]) {
cost -= costs[items[i]].value();
swap(items[i], items.back());
items.pop_back();
i--;
}
}
return {cost, items};
}
Purchase query(i64 paid) {
auto [items, cost] = transaction(paid);
for (auto x: items) buy_count[x]++;
return {paid - cost, items};
}
void shorten(Purchase purchase) {
while (purchase.items.size() != 1) {
i64 ask = purchase.cost / purchase.items.size();
shorten(process(query(ask)));
purchase = process(purchase);
}
costs[purchase.items[0]] = purchase.cost;
solve_suffix(purchase.items[0] + 1);
i64 ask = purchase.cost / purchase.items.size();
}
void solve_suffix(int start) {
if (start == N || costs[start]) return;
i64 bound = costs[start - 1].value();
shorten(process(query(bound - 1)));
}
void buy_souvenirs(int N, long long P0) {
::N = N;
costs.resize(N);
buy_count.resize(N);
costs[0] = P0;
solve_suffix(1);
for (int i = 0; i < N; i++)
while (buy_count[i] < i)
query(costs[i].value());
}
