#include "souvenirs.h"
#include <bits/stdc++.h>
#define FOR(i, a, b) for (auto i = (a); i <= (b); i++)
#define ROF(i, a, b) for (auto i = (a); i >= (b); i--)
using namespace std;
using ll = long long;
int N;
vector<bool> known;
vector<ll> P;
vector<int> C;
vector<pair<set<int>, ll>> res;
map<ll, pair<vector<int>, ll>> mp;
pair<set<int>, ll> query(ll M) {
vector<int> v; ll x;
bool f = 0;
if (mp.find(M) == mp.end()) mp[M] = transaction(M), f = 1;
tie(v, x) = mp[M];
x = M - x;
set<int> s;
for (int i : v) {
if (f) C[i]++;
if (!known[i]) s.insert(i);
else x -= P[i];
}
res.push_back({s, x});
return {s, x};
}
void buy_rest() {
FOR(i, 0, N - 1) {
assert(C[i] <= i);
while (C[i]++ < i) transaction(P[i]);
}
}
void know(int i, ll x) {
if (known[i]) return;
// assert(!known[i]);
P[i] = x, known[i] = 1;
for (auto& p : res) {
auto& s = p.first;
auto& x = p.second;
if (s.count(i)) {
s.erase(i);
x -= P[i];
}
if (s.size() == 1) know(*s.begin(), x);
}
}
void solve(int S) {
assert(known[S]);
bool all = 1;
FOR(i, S, N - 1) if (!known[i]) all = 0;
if (all) return;
if (known[S + 1]) {
solve(S + 1);
return;
}
// cout << ":: " << S << " " << P[S] << "\n";
auto [s, x] = query(P[S] - 1);
while (s.size() > 1) {
int m = s.size();
// cout << " ## " << x << " " << m << "\n";
auto [s2, x2] = query(x / m);
s = s2, x = x2;
}
if (s.empty()) {
// cout << "aa\n";
}
int i = *s.begin();
know(i, x);
ROF(i, N - 1, S) if (known[i]) solve(i);
}
void buy_souvenirs(int _N, long long P0) {
N = _N, P.resize(N), C.resize(N), known.resize(N);
know(0, P0);
solve(0);
buy_rest();
}
