#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i32 = int32_t;
static constexpr ll inf = (ll)2e18;
static constexpr i32 oth = (i32)2e9;
struct node {
i32 nxt;
i32 mini = oth;
ll sum = 0;
};
static constexpr int bv = 25;
static constexpr int mb = 9;
// arr<x,y> style: fixed bv/mb, dynamic n
static array<array<vector<node>, mb>, bv> lift;
static vector<ll> stg, win, lose, pen;
void init(signed _n, vector<signed> _s, vector<signed> _p,
vector<signed> _w, vector<signed> _l) {
int n = (int)_n;
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];
}
vector<int> par(n + 1, n);
for (int i = 0; i < n; i++) par[i] = (int)lose[i];
// allocate each (b,bit) vector to size n+1 (same as original)
for (int b = 0; b < bv; b++) {
for (int bit = 0; bit < mb; bit++) {
lift[b][bit].assign(n + 1, node{(i32)n, oth, 0});
}
}
vector<ll> c(n + 1, 0);
for (int i = 0; i < n; i++) c[i] = pen[i];
for (int b = 0; b < bv; b++) {
// bit = 0 initialization
for (int i = 0; i < n; i++) {
lift[b][0][i].nxt = (i32)par[i];
lift[b][0][i].sum = c[i];
lift[b][0][i].mini = (__lg((ll)stg[i]) == b) ? (i32)stg[i] : oth;
}
// sentinel row
for (int bit = 0; bit < mb; bit++) lift[b][bit][n].nxt = (i32)n;
// build higher bits
for (int bit = 1; bit < mb; bit++) {
for (int i = 0; i < n; i++) {
node &res = lift[b][bit][i];
res = lift[b][bit - 1][i];
for (int it = 0; it < (1 << ((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 != oth) {
ll gurt = (ll)y.mini - res.sum;
res.mini = min<i32>(res.mini, (i32)max(-1LL, gurt));
}
res.sum += y.sum;
}
}
}
// update par/c for next b
for (int i = 0; i < n; i++) {
if (__lg((ll)stg[i]) <= b) {
par[i] = (int)win[i];
c[i] = stg[i];
}
}
}
}
static inline void nxt_step(int &x, ll &z) {
if (z >= stg[x]) {
z += stg[x];
x = (int)win[x];
} else {
z += pen[x];
x = (int)lose[x];
}
}
long long simulate(signed _x, signed _z) {
int x = (int)_x;
ll z = (ll)_z;
int n = (int)lift[0][0].size() - 1;
for (int b = 0; b < bv && x != n; b++) {
for (int 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_step(x, z);
}
return z;
}
