#include "souvenirs.h"
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
//std::pair<std::vector<int>, int> transaction(long long m) {
// return {{0}, 0};
//}
struct eq {
std::vector<int> s;
long long sum;
friend bool operator<(const eq &a, const eq &b) {
if(a.s[a.s.size()-1] != b.s[b.s.size()-1]) return a.s[a.s.size()-1] < b.s[b.s.size()-1];
else return a.sum < b.sum;
};
};
void buy_souvenirs(int n, long long p0) {
//we can start by querying p0-1
std::vector<long long> ans(n, 0);
ans[0] = p0;
std::set<int> need;
for(int i = 1; i < n; ++i) need.insert(i);
std::map<int, int> cntans;
//while there exists unknown element in set
while(!need.empty()) {
int fir = *need.begin();
std::set<eq> eqs;
std::pair<std::vector<int>, long long> stemp = transaction(ans[fir-1]-1);
eq eq1 = {stemp.first, ans[fir-1]-1-stemp.second};
eqs.insert(eq1);
for(auto it : eq1.s) ++cntans[it];
//while we can still deduce some element from an initial equation
while(!eqs.empty()) {
auto [vals, sum] = *eqs.begin();
int ck = vals.size();
long long nxt = sum/ck;
//consider the next "step"
std::pair<std::vector<int>, long long> ctemp = transaction(nxt);
eq eqn = {ctemp.first, nxt-ctemp.second};
for(auto it : eqn.s) ++cntans[it];
std::set<int> process;
if(ctemp.first.size() == 1) {
//we have found a value and can insert into process
ans[eqn.s[0]] = eqn.sum;
process.insert(eqn.s[0]);
need.erase(eqn.s[0]);
} else {
eqs.insert(eqn);
}
//keep on deducing values from previously found elements when possible
while(!process.empty()) {
std::set<eq> neq;
int cur = *process.begin();
auto it = eqs.begin();
while(it != eqs.end()) {
std::vector<int> ns;
long long tsum = it->sum;
for(auto v : it->s) {
if(v != cur) ns.push_back(v);
else tsum -= ans[v];
}
if(ns.size() == 1) {
ans[ns[0]] = tsum;
process.insert(ns[0]);
need.erase(ns[0]);
} else {
neq.insert({ns, tsum});
}
++it;
}
eqs = neq;
}
}
}
for(int i = 1; i < n; ++i) {
for(int j = cntans[i]; j <= i; ++j) transaction(ans[i]);
}
}
