#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
static int n;
static vector<ll> val;
static vector<int> bought;
static vector<vector<int>> unk;
static vector<ll> sumunk;
static inline ll guess_min_first(ll S, int k){
__int128 two = (__int128)2 * S;
ll q = (ll)(two / k);
ll z = (q + 1 - k) / 2;
if(z < 1) z = 1;
return z;
}
static void add_eq(ll M){
auto res = transaction(M);
for(int x: res.first) bought[x]++;
int y = res.first[0];
ll S = M - res.second;
for(int x: res.first){
if(val[x] != -1) S -= val[x];
else unk[y].push_back(x);
}
sumunk[y] = S;
}
static void remove_last(){
int last = n - 1;
ll v = val[last];
for(int i=0;i<n;i++){
if(unk[i].empty()) continue;
auto &dq = unk[i];
if(!dq.empty() && dq.back() == last){
dq.pop_back();
sumunk[i] -= v;
}
}
n--;
}
static void solve_from(int x){
if(x >= n-1) return;
add_eq(val[x] - 1);
int start = x + 1;
while(true){
int lst = -1;
for(int i=start;i<n;i++){
if(val[i]==-1 && !unk[i].empty()) lst = i;
}
if(lst == -1) break;
if((int)unk[lst].size() == 1){
int id = unk[lst][0];
val[id] = sumunk[lst];
unk[lst].clear();
if(id < n-1) solve_from(id);
while(n>=2 && val[n-1] != -1) remove_last();
}else{
ll p = guess_min_first(sumunk[lst], (int)unk[lst].size());
if(p >= val[0]) p = val[0] - 1;
if(p < 1) p = 1;
add_eq(p);
}
}
}
void buy_souvenirs(int N, long long P0){
n = N;
val.assign(n, -1);
bought.assign(n, 0);
unk.assign(n, {});
sumunk.assign(n, -1);
val[0] = P0;
solve_from(0);
while(n>=2 && val[n-1] != -1) remove_last();
for(int i=1;i<N;i++){
while(bought[i] < i){
auto res = transaction(val[i]);
for(int x: res.first) bought[x]++;
}
}
}
