#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ll = long long;
const int INF = 1e9;
const int N = 4e5+7;
const int B = 16;
const int W = 7; // exp = B^0, B^1, ..., B^{W-1}
const int L = 24; // jump 2^0, 2^1, ..., d^{L-1}
struct Jump {
int go, max_exp, fadd;
} jmp[W][L][N];
ll cost_last[N];
int n;
vi s, p, w, l;
void unite(const Jump& a, const Jump& b, Jump& res) {
res.fadd = a.fadd + b.fadd;
res.go = b.go;
res.max_exp = min(a.max_exp, b.max_exp - a.fadd);
res.max_exp = max(res.max_exp, 0);
res.fadd = min(res.fadd, INF);
}
void init(int _n, vi _s, vi _p, vi _w, vi _l) {
n = _n;
s = _s;
p = _p;
w = _w;
l = _l;
for (int i = n; i--; ) {
cost_last[i] = cost_last[w[i]] + s[i];
}
for (int jexp = 0, exp = 1; jexp < W; ++jexp, exp *= B) {
for (int i = 0; i < n; ++i) {
Jump& jm = jmp[jexp][0][i];
if (exp >= s[i]) {
jm.go = w[i];
jm.max_exp = INF;
jm.fadd = s[i];
} else {
jm.go = l[i];
jm.max_exp = s[i] - 1;
jm.fadd = p[i];
}
}
jmp[jexp][0][n].fadd = 0;
jmp[jexp][0][n].go = n;
jmp[jexp][0][n].max_exp = INF;
for (int k = 1; k < L; ++k) {
for (int i = 0; i < n; ++i) {
const Jump& ja = jmp[jexp][k-1][i];
unite(ja, jmp[jexp][k-1][ja.go], jmp[jexp][k][i]);
}
}
}
return;
}
ll simulate(int x, int _z) {
ll z = _z;
while (z < 1e7) {
int jexp = 0, exp = 1;
while ((ll)exp*B <= z) exp *= B, jexp++;
for (int t = L; t--; ) {
Jump& jm = jmp[jexp][t][x];
if (z <= jm.max_exp) {
z += jm.fadd;
x = jm.go;
}
}
if (x == n) return z;
if (z < s[x]) {
z += p[x];
x = l[x];
} else {
z += s[x];
x = w[x];
}
}
z += cost_last[x];
return z;
}
