#include "souvenirs.h"
#include<bits/stdc++.h>
using namespace std;
void buy_souvenirs(int n, long long P0){
vector<long long> P(n, P0);
vector<int> cnt(n);
function<pair<vector<int>, long long>(long long, int)> query = [&](long long m, int k){
pair<vector<int>, long long> res = transaction(m);
vector<int> &c = res.first;
long long p = res.second;
long long used = m - p;
for(int i: c) cnt[i]++;
while(!c.empty() && c.back() >= k){
used -= P[c.back()];
c.pop_back();
}
assert(!c.empty());
return make_pair(c, used);
};
function<int(long long, int)> get = [&](long long X, int k){
pair<vector<int>, long long> Q = query(X, k);
vector<int> S = Q.first;
long long sm = Q.second;
int i = S[0];
while((int)S.size() > 1){
k = get((sm - 1) / (int)S.size(), k);
while(!S.empty() && S.back() >= k){
sm -= P[S.back()];
S.pop_back();
}
assert(!S.empty());
}
P[i] = sm;
if(k > i + 1) get(P[i] - 1, k);
return i;
};
get(P[0] - 1, n);
for(int i = 0; i < n; i++){
while(cnt[i] < i){
transaction(P[i]);
cnt[i]++;
}
}
}
