#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MXN = 5e4+3, LOGS=24, LOGN=16;
const ll inf = 1e18;
const int inf32 = 1e9;
int n, s[MXN], p[MXN], w[MXN], l[MXN], f[LOGS][LOGN][MXN];
ll sum[LOGS][LOGN][MXN], dp[MXN];
int mn[LOGS][LOGN][MXN];
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
::n = n;
assert(n<=50000);
for(int i=0; i<n; i++) {
::s[i] = s[i];
::p[i] = p[i];
::w[i] = w[i];
::l[i] = l[i];
}
for(int t=0; t<LOGS; t++) {
for(int i=0; i<LOGN; i++) f[t][i][n] = n;
for(int i=0; i<n; i++) {
f[t][0][i] = (s[i]<(1<<t) ? w[i] : l[i]),
sum[t][0][i] = (s[i]<(1<<t) ? s[i] : p[i]);
mn[t][0][i] = ((1<<t)<=s[f[t][0][i]] && s[f[t][0][i]]<(1<<(t+1))
? max(0ll, s[f[t][0][i]]-sum[t][0][i])
: inf32);
}
for(int i=1; i<LOGN; i++)
for(int j=0; j<n; j++) {
f[t][i][j] = f[t][i-1][f[t][i-1][j]];
sum[t][i][j] = sum[t][i-1][j] + sum[t][i-1][f[t][i-1][j]];
mn[t][i][j] = mn[t][i-1][f[t][i-1][j]]==inf32
? mn[t][i-1][j]
: min(mn[t][i-1][j], (int)max(0ll, mn[t][i-1][f[t][i-1][j]]-sum[t][i-1][j]));
}
}
dp[n] = 0;
for(int i=n-1; i>=0; i--)
dp[i] = dp[w[i]] + s[i];
}
ll simulate(int x, int z) {
ll ans=z;
while(x<n) {
int t = min((int)__lg(ans), LOGS-1);
if(!((1<<t)<=s[x] && s[x]<(1<<(t+1))) || s[x]>ans)
for(int i=LOGN-1; i>=0; i--)
if(f[t][i][x]!=n && ans+sum[t][i][x]<(1<<(t+1)) && (mn[t][i][x]==inf32 || mn[t][i][x]>ans)) {
ans += sum[t][i][x];
x = f[t][i][x];
}
while(ans<(1<<(t+1))) {
if(ans>=s[x]) {
ans += s[x];
x = w[x];
}
else {
ans += p[x];
x = l[x];
}
if(x==n) return ans;
}
if(ans>=1e7) return dp[x] + ans;
}
return ans + dp[x];
}
