#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
static int n;
static long long p0;
static vector<long long> price;
static vector<long long> bought;
static pair<vector<int>, long long> ask(long long M){
auto res = transaction(M);
for(int x : res.first) bought[x]++;
return res;
}
static void deduce(int idx, long long limit){
if(idx <= 0 || idx >= n) return;
if(price[idx] != -1) return;
auto res = ask(limit);
if(res.first.empty()) return;
long long spent = limit - res.second;
int id = res.first[0];
price[id] = spent;
}
void buy_souvenirs(int N, long long P0){
n = N;
p0 = P0;
price.assign(n, -1);
bought.assign(n, 0);
price[0] = P0;
for(int i = 1; i < n; i++){
long long lim = price[i-1] - 1;
if(lim <= 0) break;
deduce(i, lim);
}
for(int i = 1; i < n; i++){
if(price[i] <= 0) continue;
while(bought[i] < i){
ask(price[i]);
}
}
}
