#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
using vpi = vector<pi>;
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define x first
#define y second
#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i= (a); i < (b); i++)
#define per(i,a,b) for(int i = (b) - 1; i >= (a); i--)
#ifdef LOCAL
template<class A, class B> auto& operator<<(auto &o, pair<A, B> p) { return o << '(' << p.x << ", " << p.y << ')'; }
auto& operator<<(auto& o, auto a) {
o << "{";
for (auto b : a) o << b << ", ";
return o << "}";
}
void dump(auto... x) { ((cerr << x << ", "), ...) << "\n"; }
#define debug(x...) cerr << "[" #x "]: ", dump(x)
#else
#define debug(...) ;
#endif
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int MAXN = 4e5 + 5, LOGZ = 25, DIV = 4;
const ll INF = 1e18 + 1;
int n;
vi s,p,w,l;
int dest[MAXN][LOGZ / DIV + 1][LOGZ];
ll gain[MAXN][LOGZ / DIV + 1][LOGZ], min_req[MAXN][LOGZ / DIV + 1][LOGZ];
void init(int _n, vi _s, vi _p, vi _w, vi _l) {
n = _n; s = _s, p = _p, w = _w, l = _l;
rep(t,0,LOGZ / DIV + 1) {
int threshold = 1;
rep(it,0,DIV) threshold = threshold * (1 << t);
rep(i,0,n) {
dest[i][t][0] = (s[i] <= threshold? w[i]:l[i]);
gain[i][t][0] = (s[i] <= threshold? s[i]:p[i]);
min_req[i][t][0] = (s[i] <= threshold? INF:s[i]);
}
dest[n][t][0] = n;
gain[n][t][0] = 0;
min_req[n][t][0] = 0;
rep(j,1,LOGZ) {
rep(i,0,n) {
int k = dest[i][t][j-1];
dest[i][t][j] = dest[k][t][j-1];
gain[i][t][j] = gain[k][t][j-1] + gain[i][t][j-1];
ll tmp = min_req[k][t][j-1] - gain[i][t][j-1];
min_req[i][t][j] = min(min_req[i][t][j-1], tmp);
}
dest[n][t][j] = n;
gain[n][t][j] = 0;
min_req[n][t][j] = 0;
}
}
return;
}
ll simulate(int x, int z) {
ll strength = z;
debug("start", x, strength);
rep(t,0,LOGZ / DIV + 1) {
rep(it,0,(1<<DIV)) {
per(j,0,LOGZ) {
if (min_req[x][t][j] > strength) {
strength += gain[x][t][j];
x = dest[x][t][j];
debug("jump", t, j, x, strength);
}
}
if (x == n) break;
debug("from", t, x, strength, s[x], p[x], w[x], l[x]);
assert(s[x] <= strength);
strength += s[x];
x = w[x];
debug("to", x, strength);
if (x == n) break;
}
if (x == n) break;
}
assert(x == n);
return strength;
}
