#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
vector<int> s, p, w, l;
const int MAXBIT = 30, MAXN = 4e5+5;
int winskip[MAXBIT][MAXN], loseskip[MAXBIT][MAXN];
ll winval[MAXBIT][MAXN], loseval[MAXBIT][MAXN], wingain[MAXBIT][MAXN], losegain[MAXBIT][MAXN];
void init(int _n, vector<int> _s, vector<int> _p, vector<int> _w, vector<int> _l) {
n = _n; s = _s; p = _p; w = _w; l = _l;
s.push_back(0); p.push_back(0); w.push_back(n); l.push_back(n);
for (int i = 0; i <= n; i++) {
winskip[0][i] = w[i];
winval[0][i] = s[i];
wingain[0][i] = s[i];
loseskip[0][i] = l[i];
loseval[0][i] = s[i];
losegain[0][i] = p[i];
}
for (int j = 0; j < MAXBIT-1; j++) {
for (int i = 0; i <= n; i++) {
int skw = winskip[j][i];
winskip[j+1][i] = winskip[j][skw];
winval[j+1][i] = max(winval[j][i], winval[j][skw] - wingain[j][i]);
wingain[j+1][i] = wingain[j][i] + wingain[j][skw];
int skl = loseskip[j][i];
loseskip[j+1][i] = loseskip[j][skl];
loseval[j+1][i] = min(loseval[j][i], loseval[j][skl] - losegain[j][i]);
losegain[j+1][i] = losegain[j][i] + losegain[j][skl];
}
}
}
long long simulate(int x, int _z) {
ll z = _z;
// Winning steps
while (true) {
int targ = x;
ll val = z;
if (val >= s[targ] && w[targ] == n) return val+s[targ];
if (val < s[targ] && l[targ] == n) return val+p[targ];
for (int j = MAXBIT-1; j >= 0; j--) {
if (loseval[j][targ] > val && loseskip[j][targ] != n) {
val += losegain[j][targ];
targ = loseskip[j][targ];
}
}
if (val >= s[targ] && w[targ] == n) return val+s[targ];
if (val < s[targ] && l[targ] == n) return val+p[targ];
for (int j = MAXBIT-1; j >= 0; j--) {
if (winval[j][targ] <= val && winskip[j][targ] != n) {
val += wingain[j][targ];
targ = winskip[j][targ];
}
}
if (val >= s[targ] && w[targ] == n) return val+s[targ];
if (val < s[targ] && l[targ] == n) return val+p[targ];
x = targ;
z = val;
}
}
