#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
namespace{
#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define F0R(i, r) FOR(i, 0, r)
#define FORD(i, l, r) for(int i = (r) - 1; i < >= (l); --i)
#define F0RD(i, r) FORD(i, l, r)
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
#define uniquify(v) v.erase(unique(all(v)), end(v))
#define tcT template<class T
#define dbg(x) "[" #x " = " << (x) << "]"
tcT> bool minimize(T& a, const T& b){ return (a > b ? a = b, 1 : 0); }
tcT> bool maximize(T& a, const T& b){ return (a < b ? a = b, 1 : 0); }
tcT> using vc = vector<T>;
tcT> using vvc = vc<vc<T>>;
using uint = unsigned int;
using ll = long long;
using db = double;
using ull = unsigned long long;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vc<int>;
using vl = vc<ll>;
using vpi = vc<pi>;
using vpl = vc<pl>;
using vvi = vvc<int>;
using vvl = vvc<ll>;
using vvpi = vvc<pi>;
using vvpl = vvc<pl>;
}
void buy_souvenirs(int N, long long P0) {
if(N == 2){
transaction(P0 - 1);
return;
}
vi called(N);
auto updateCall = [&](vi S){
for(auto u : S) {
++called[u];
assert(called[u] <= u);
}
};
vl P(N, -1);
P[0] = P0;
ll X = P0 - 1;
while(true){
auto [S, m] = transaction(X);
updateCall(S);
if(sz(S) == 1){
P[S[0]] = X - m;
if(S[0] == N - 1) break;
X = P[S[0]] - 1;
} else{
X /= sz(S);
}
}
if(all_of(all(P), [&](ll i){ return i != -1; })){
while(true){
ll sum = 0;
F0R(i, N){
if(called[i] < i){
sum += P[i];
}
}
if(sum == 0) break; //all done
auto [S, m] = transaction(sum);
updateCall(S);
}
return;
}
}
