#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int SIZE = 2;
const int LOG = 24;
struct Data{
int pos, need;
ll sum;
};
Data combine(Data a, Data b){
Data c;
c.pos = b.pos;
c.sum = a.sum + b.sum;
if(b.need == -1) c.need = a.need;
else if(b.need <= a.sum) c.need = 0;
else if(a.need != -1) c.need = min(a.need, b.need-(int)a.sum);
else c.need = b.need-(int)a.sum;
return c;
}
int n;
vector<int> s, p, w, l;
Data jump[LOG/SIZE][LOG][int(4e5+1)];
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_;
for(int i = 0; i < LOG/SIZE; i++){
for(int j = 0; j < n; j++){
if(s[j] <= (1<<(i*SIZE))) jump[i][0][j] = {w[j], -1, s[j]};
else jump[i][0][j] = {l[j], s[j], p[j]};
}
jump[i][0][n] = {n, 0, 0};
for(int k = 1; k < LOG; k++){
for(int j = 0; j <= n; j++){
jump[i][k][j] = combine(jump[i][k-1][j], jump[i][k-1][jump[i][k-1][j].pos]);
}
}
}
}
ll simulate(int x, int z) {
ll ans = z;
while(x != n){
if(ans >= s[x]){
ans += s[x];
x = w[x];
continue;
}
int layer;
for(layer = 1; layer <= LOG/SIZE && ans >= (1<<(layer*SIZE)); layer++);
layer--;
Data d{x, -1, ans};
for(int k = LOG-1; k >= 0; k--){
Data d2 = combine(d, jump[layer][k][d.pos]);
if(d2.need > 0) d = d2;
}
ans = d.sum;
x = d.pos;
}
return ans;
}
