#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; // index, fits in 32-bit (<= 400001)
ll sum; // if safe (see note below)
ll mini; // still 64-bit
};
#pragma pack(pop)
static node lift[bv][mb][MAXN];
vector<ll> stg, win, lose, pen;
void init(signed _n, vector<signed> _s, vector<signed> _p,
vector<signed> _w, vector<signed> _l) {
ll n = _n;
vector<ll> s(n), p(n), w(n), l(n);
for (ll i = 0; i < n; i++)
s[i] = _s[i], p[i] = _p[i], w[i] = _w[i], l[i] = _l[i];
stg = s;
win = w;
lose = l;
pen = p;
vector<ll> par(n + 1, n);
for (ll i = 0; i < n; i++)
par[i] = l[i];
vector<ll> c(n + 1, 0);
for (ll i = 0; i < n; i++)
c[i] = p[i];
for (ll b = 0; b < bv; b++) {
for (ll i = 0; i < n; i++) {
lift[b][0][i].nxt = par[i];
lift[b][0][i].sum = c[i];
if (__lg(s[i]) == b)
lift[b][0][i].mini = s[i];
else
lift[b][0][i].mini = inf;
}
for (ll bit = 0; bit < mb; bit++)
lift[b][bit][n].nxt = n;
for (ll bit = 1; bit < mb; bit++)
for (ll i = 0; i < n; i++) {
node &res = lift[b][bit][i];
res = lift[b][bit - 1][i];
for (ll it = 0;
it < (1LL << ((bv + mb - 1) / mb)) - 1;
it++) {
node y = lift[b][bit - 1][res.nxt];
res.nxt = lift[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 (ll i = 0; i < n; i++)
if (__lg(s[i]) <= b)
par[i] = w[i], c[i] = s[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 = MAXN - 1; // 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][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][x];
}
}
nxt(x, z);
}
return z;
}
