#include "dungeons.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
typedef pair<int32_t, int32_t> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxn 400010
#define INF (ll)1e9
#define MOD 1000000007
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;
int twokw[maxn][30], twokl[maxn][30], valw[maxn][30], vall[maxn][30], mnw[maxn][30], mxl[maxn][30];
int S[maxn], P[maxn], W[maxn], L[maxn];
int N;
void init(int32_t n, std::vector<int32_t> s, std::vector<int32_t> p, std::vector<int32_t> w, std::vector<int32_t> l) {
N = n;
FOR(i,0,N-1){
S[i] = s[i], P[i] = p[i], W[i] = w[i], L[i] = l[i];
}
FOR(i,0,N-1){
twokw[i][0] = w[i], twokl[i][0] = l[i];
vall[i][0] = p[i], valw[i][0] = s[i];
mxl[i][0] = s[i]-1, mnw[i][0] = s[i];
}
twokw[N][0] = twokl[N][0] = N;
FOR(k,1,29){
FOR(i,0,N){
twokw[i][k] = twokw[twokw[i][k-1]][k-1];
twokl[i][k] = twokl[twokl[i][k-1]][k-1];
valw[i][k] = valw[i][k-1] + valw[twokw[i][k-1]][k-1];
vall[i][k] = vall[i][k-1] + vall[twokl[i][k-1]][k-1];
mnw[i][k] = max(mnw[i][k-1], mnw[twokw[i][k-1]][k-1] - valw[i][k-1]);
mxl[i][k] = min(mxl[i][k-1], mxl[twokl[i][k-1]][k-1] - vall[i][k-1]);
}
}
return;
}
long long simulate(int32_t x, int32_t z) {
while (1){
if (z >= S[x]){
DEC(k,29,0) if (twokw[x][k] < N && z >= mnw[x][k]){
//cout << k << ' ';
z += valw[x][k];
x = twokw[x][k];
}
}else{
DEC(k,29,0) if (twokl[x][k] < N && z <= mxl[x][k]){
//cout << k << ' ';
z += vall[x][k];
x = twokl[x][k];
}
}
//cout << x << ' ' << z << '\n';
if (z >= S[x] && W[x] == N) return z + S[x];
if (z < S[x] && L[x] == N) return z + P[x];
}
return 0;
}
