#include "bits/stdc++.h"
#include "dungeons.h"
using namespace std;
#define ll long long
const int inf = 2e9 + 5;
const int N = 1e6 + 5;
const int K = 24;
vector<vector<int> > nxt, add, jumpw, jumpl;
vector<vector<ll> > sumw, mxw, suml, mnl;
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l){
nxt.resize(n+1);
add.resize(n+1);
for(int i = 0; i < n; i++){
nxt[i].resize(2);
nxt[i][0] = l[i];
nxt[i][1] = w[i];
add[i].resize(2);
add[i][0] = p[i];
add[i][1] = s[i];
}
nxt[n].resize(2);
add[n].resize(2);
nxt[n][0] = nxt[n][1] = n;
add[n][0] = add[n][1] = 0;
jumpw.resize(n+1);
sumw.resize(n+1);
mxw.resize(n+1);
for(int i = 0; i <= n; i++){
jumpw[i].resize(K);
sumw[i].resize(K);
mxw[i].resize(K);
jumpw[i][0] = nxt[i][1];
sumw[i][0] = add[i][1];
mxw[i][0] = add[i][1];
}
for(int i = 1; i < K; i++){
for(int j = 0; j <= n; j++){
jumpw[j][i] = jumpw[jumpw[j][i-1]][i-1];
sumw[j][i] = sumw[j][i-1] + sumw[jumpw[j][i-1]][i-1];
mxw[j][i] = max(mxw[j][i-1], mxw[jumpw[j][i-1]][i-1] - sumw[j][i-1]);
}
}
jumpl.resize(n+1);
suml.resize(n+1);
mnl.resize(n+1);
for(int i = 0; i <= n; i++){
jumpl[i].resize(K);
suml[i].resize(K);
mnl[i].resize(K);
jumpl[i][0] = nxt[i][0];
suml[i][0] = add[i][0];
mnl[i][0] = add[i][1];
}
for(int i = 1; i < K; i++){
for(int j = 0; j <= n; j++){
jumpl[j][i] = jumpl[jumpl[j][i-1]][i-1];
suml[j][i] = suml[j][i-1] + suml[jumpl[j][i-1]][i-1];
mnl[j][i] = min(mnl[j][i-1], mnl[jumpl[j][i-1]][i-1] - suml[j][i-1]);
}
}
return;
}
long long simulate(int x, int z){
int n = nxt.size() - 1;
long long cur = z;
while(x != n){
for(int j = K-1; j >= 0; j--){
if(mxw[x][j] <= cur){
cur += sumw[x][j];
x = jumpw[x][j];
}
}
for(int j = K-1; j >= 0; j--){
if(mnl[x][j] > cur){
cur += suml[x][j];
x = jumpl[x][j];
}
}
}
return cur;
}
