/*
Observation 1: After the first consecutive losses, you will lose at no more than O(log(s)) positions.
*/
#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;
// Initial losing
for (int j = MAXBIT-1; j >= 0; j--) {
if (loseval[j][x] > z && loseskip[j][x] != n) {
z += losegain[j][x];
x = loseskip[j][x];
}
}
if (z >= s[x] && w[x] == n) return z+s[x];
if (z < s[x] && l[x] == n) return z+p[x];
// Winning steps
while (true) {
if (z >= s[x] && w[x] == n) return z+s[x];
if (z < s[x] && l[x] == n) return z+p[x];
int targ;
ll val;
bool islose;
if (z < s[x]) {
targ = l[x];
val = z + p[x];
islose = true;
} else {
targ = w[x];
val = z + s[x];
islose = false;
}
if (val >= s[targ] && w[targ] == n) return val+s[targ];
if (val < s[targ] && l[targ] == n) return val+p[targ];
int tx = targ;
ll tz = val;
for (int j = MAXBIT-1; j >= 0; j--) {
if (loseval[j][tx] > z && loseskip[j][tx] != n) {
tz += losegain[j][tx];
tx = loseskip[j][tx];
}
}
if (tz != val) {
x = tx;
z = tz;
continue;
}
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];
if (targ == x && islose) {
ll gain = val - z;
ll iter = (s[x]-z+gain-1)/gain;
z += gain*iter;
} else {
x = targ;
z = val;
}
}
}
