#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pii pair<ll,ll>
#define ff first
#define ss second
const ll inf = 2e18;
const ll bv = 25;
const ll mb = 9;
const ll MAXN = 400001;
#pragma pack(push, 1)
struct node {
signed nxt = 0; // default
ll sum = 0; // default
ll mini = inf; // default
};
#pragma pack(pop)
// allocate dynamically to avoid huge global object / linker pain
static node *lift = nullptr;
static inline node& L(int b, int bit, int i) {
return lift[( (b * mb + bit) * MAXN + i )];
}
vector<ll> stg, win, lose, pen;
void init(signed _n, vector<signed> _s, vector<signed> _p,
vector<signed> _w, vector<signed> _l) {
ll n_ll = _n;
int n = (int)n_ll;
stg.assign(n, 0);
pen.assign(n, 0);
win.assign(n, 0);
lose.assign(n, 0);
for (int i = 0; i < n; i++) {
stg[i] = _s[i];
pen[i] = _p[i];
win[i] = _w[i];
lose[i] = _l[i];
}
// allocate once
if (!lift) {
lift = new node[(size_t)bv * mb * MAXN];
}
// set defaults only for indices we will actually use: i in [0..n]
// (huge win vs filling all MAXN every time)
for (int b = 0; b < bv; b++) {
for (int bit = 0; bit < mb; bit++) {
for (int i = 0; i <= n; i++) {
auto &t = L(b, bit, i);
t.nxt = n; // sensible default sentinel
t.sum = 0;
t.mini = inf;
}
}
}
vector<int> par(n + 1, n);
for (int i = 0; i < n; i++) par[i] = (int)lose[i];
vector<ll> c(n + 1, 0);
for (int i = 0; i < n; i++) c[i] = pen[i];
for (int b = 0; b < bv; b++) {
for (int i = 0; i < n; i++) {
L(b, 0, i).nxt = (signed)par[i];
L(b, 0, i).sum = c[i];
L(b, 0, i).mini = (__lg(stg[i]) == b) ? stg[i] : inf;
}
for (int bit = 0; bit < mb; bit++)
L(b, bit, n).nxt = (signed)n;
for (int bit = 1; bit < mb; bit++) {
for (int i = 0; i < n; i++) {
node &res = L(b, bit, i);
res = L(b, bit - 1, i);
for (int it = 0; it < (1 << ((bv + mb - 1) / mb)) - 1; it++) {
node y = L(b, bit - 1, res.nxt);
res.nxt = L(b, bit - 1, res.nxt).nxt;
if (y.mini != inf) {
ll gurt = y.mini - res.sum;
res.mini = min(res.mini, max(-1LL, gurt));
}
res.sum += y.sum;
}
}
}
for (int i = 0; i < n; i++)
if (__lg(stg[i]) <= b)
par[i] = (int)win[i], c[i] = stg[i];
}
}
void nxt(ll &x, ll &z)
{
if (z >= stg[x])
z += stg[x], x = win[x];
else
z += pen[x], x = lose[x];
}
long long simulate(signed _x, signed _z) {
ll x = _x;
ll z = _z;
ll n = stg.size(); // terminal index assumed at n
for (ll b = 0; b < bv && x != n; b++) {
for (ll bit = mb - 1; bit >= 0; bit--) {
node cur = lift[b][bit][(ll)x];
while ((b == bv - 1 || cur.sum + z < (1LL << (b + 1))) &&
cur.nxt != n &&
(cur.mini > z)) {
x = cur.nxt;
z += cur.sum;
cur = lift[b][bit][(ll)x];
}
}
nxt(x, z);
}
return z;
}
