#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
#define I signed
#define int long long
const int INF = 1e18;
void buy_souvenirs(I N, int P0) {
vector<int> cnt(N);
map<int, vector<int>> bought; // x1, [S, {X}]
vector<int> P(N, 0); P[0] = P0;
int c = P0-1;
while(true) {
pair<vector<I>, int> ret = transaction(c);
int s = c - ret.second;
int x1 = ret.first[0];
bought[x1].push_back(s);
for(int x: ret.first) {
bought[x1].push_back(x);
cnt[x]++;
}
if (ret.first.size() == 1) c = s-1;
else c = s/ret.first.size();
if (x1 == N-1) break;
}
P[N-1] = bought[N-1][0];
for(int j = N-1; j > 1; j--) {
if (bought.count(j-1)) {
int s = bought[j-1][0];
for(int k = 1; k < bought[j-1].size()-1; k++) {
s -= P[bought[j-1][1+k]];
}
P[j-1] = s;
} else {
pair<vector<I>, int> ret = transaction(2 * P[j]);
int s = 2 * P[j] - ret.second;
for(int x: ret.first) {
s -= P[x];
cnt[x]++;
}
P[j-1] = s;
}
}
for(int i = 0; i < N; i++) {
while(cnt[i] < i) {transaction(P[i]); cnt[i]++;}
}
}
