#include "dungeons.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
using namespace std;
const int N = 400'010;
const int lg = 24;
const int S = 10;
int nxt[S][lg][N];
int add[S][lg][N];
int mn[S][lg][N];
int mx[S][lg][N];
const int inf = 1e9+10;
vector<int> s, p, w, l;
vector<int> cmp, scmp;
int n;
ll wn[N];
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
::n = n;
::s = s;
::p = p;
::w = w;
::l = l;
Loop (i,0,S)
cmp.push_back(64<<(2*i));
Loop (i,0,n)
scmp.push_back(lower_bound(cmp.begin(), cmp.end(), s[i]) - cmp.begin());
Loop (k,0,cmp.size()) {
Loop (i,0,n) {
nxt[k][0][i] = (scmp[i] < k? w[i]: l[i]);
add[k][0][i] = (scmp[i] < k? s[i]: p[i]);
mn[k][0][i] = (scmp[i] < k? s[i]: 0);
mx[k][0][i] = (scmp[i] < k? inf: s[i]);
}
nxt[k][0][n] = n;
Loop (j,0,lg-1) Loop (i,0,n+1) {
nxt[k][j+1][i] = nxt[k][j][nxt[k][j][i]];
add[k][j+1][i] = add[k][j][i] + add[k][j][nxt[k][j][i]];
if (add[k][j+1][i] > inf) {
add[k][j+1][i] = inf;
} else {
mn[k][j+1][i] = max(mn[k][j][i], mn[k][j][nxt[k][j][i]] - add[k][j][i]);
mx[k][j+1][i] = min(mx[k][j][i], mx[k][j][nxt[k][j][i]] - add[k][j][i]);
}
}
}
wn[n] = 0;
LoopR (i,0,n)
wn[i] = wn[w[i]] + s[i];
}
long long simulate(int x, int z) {
ll val = z;
int k = 0;
while (val < 64 && x != n) {
if (val < s[x]) {
val += p[x];
x = l[x];
} else {
val += s[x];
x = w[x];
}
}
for (;;) {
LoopR (i,0,lg) {
if (mn[k][i][x] <= val && val < mx[k][i][x]) {
val += add[k][i][x];
x = nxt[k][i][x];
}
}
if (x == n)
break;
assert(val >= s[x]);
if (val < s[x]) {
val += p[x];
x = l[x];
} else {
val += s[x];
x = w[x];
}
k = upper_bound(cmp.begin(), cmp.end(), val) - cmp.begin();
if (k == S) {
val += wn[x];
break;
}
}
return val;
}
