#include <bits/stdc++.h>
using namespace std;
// The grader provides this.
pair<vector<int>, long long> transaction(long long M);
namespace {
const long double EPS = 1e-18L;
struct EquationSystem {
int vars; // number of unknowns = N-1
vector<vector<long double>> a; // augmented matrix: vars coeffs + rhs
EquationSystem(int n = 0) : vars(n) {}
void add_equation(const vector<int>& row01, long long rhs) {
vector<long double> row(vars + 1, 0);
for (int i = 0; i < vars; ++i) row[i] = row01[i];
row[vars] = (long double)rhs;
a.push_back(row);
}
int rank_only() const {
vector<vector<long double>> b = a;
int n = (int)b.size();
int m = vars;
int r = 0;
for (int c = 0; c < m && r < n; ++c) {
int piv = -1;
for (int i = r; i < n; ++i) {
if (fabsl(b[i][c]) > EPS) {
piv = i;
break;
}
}
if (piv == -1) continue;
swap(b[r], b[piv]);
long double div = b[r][c];
for (int j = c; j <= m; ++j) b[r][j] /= div;
for (int i = 0; i < n; ++i) {
if (i == r) continue;
if (fabsl(b[i][c]) <= EPS) continue;
long double f = b[i][c];
for (int j = c; j <= m; ++j) b[i][j] -= f * b[r][j];
}
++r;
}
return r;
}
vector<long long> solve_unique() const {
vector<vector<long double>> b = a;
int n = (int)b.size();
int m = vars;
vector<int> where(m, -1);
int r = 0;
for (int c = 0; c < m && r < n; ++c) {
int piv = -1;
for (int i = r; i < n; ++i) {
if (fabsl(b[i][c]) > EPS) {
piv = i;
break;
}
}
if (piv == -1) continue;
swap(b[r], b[piv]);
where[c] = r;
long double div = b[r][c];
for (int j = c; j <= m; ++j) b[r][j] /= div;
for (int i = 0; i < n; ++i) {
if (i == r) continue;
if (fabsl(b[i][c]) <= EPS) continue;
long double f = b[i][c];
for (int j = c; j <= m; ++j) b[i][j] -= f * b[r][j];
}
++r;
}
vector<long long> ans(m, 0);
for (int i = 0; i < m; ++i) {
// unique solution is guaranteed when rank == m
long double val = b[where[i]][m];
ans[i] = llround(val);
}
return ans;
}
};
}
void buy_souvenirs(int N, long long P0) {
if (N == 1) return; // not possible per constraints, but harmless
int vars = N - 1; // unknowns: P[1..N-1]
EquationSystem sys(vars);
long long M = P0 - 1;
while (true) {
auto res = transaction(M);
const vector<int>& L = res.first;
long long R = res.second;
long long spent = M - R;
vector<int> row(vars, 0);
for (int t : L) {
// type 0 is impossible because M < P0
if (t >= 1) row[t - 1] = 1;
}
sys.add_equation(row, spent);
if (sys.rank_only() == vars) {
vector<long long> price = sys.solve_unique(); // price[i-1] = P[i]
for (int i = 1; i < N; ++i) {
for (int cnt = 0; cnt < i; ++cnt) {
transaction(price[i - 1]);
}
}
return;
}
M = spent - 1;
}
}
