#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int Nglobal;
ll P[110];
int bought_count[110];
pair<vector<int>, ll> do_query(ll M) {
auto res = transaction(M);
for (int idx : res.first) {
bought_count[idx]++;
}
return res;
}
int dfs(ll val, int Mlimit) {
auto pr = do_query(val);
vector<int> V = pr.first;
ll R = pr.second;
int cur = V[0];
ll T = val - R;
while (true) {
while (!V.empty() && V.back() >= Mlimit) {
T -= P[V.back()];
V.pop_back();
}
if ((int)V.size() == 1) break;
int k = (int)V.size();
ll newVal = (T - 1) / k;
int newLimit = dfs(newVal, Mlimit);
Mlimit = newLimit;
}
P[cur] = T;
return cur;
}
void buy_souvenirs(int N, long long P0) {
Nglobal = N;
memset(bought_count, 0, sizeof(bought_count));
dfs(P0 - 1, N);
for (int i = 1; i < N; ++i) {
for (int times = bought_count[i]; times < i; ++times) {
do_query(P[i]);
}
}
}
