#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <limits.h>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <deque>
#include <map>
#include <chrono>
#include <random>
#include <bitset>
#include <tuple>
#include "dungeons.h"
#define SZ(x) int(x.size())
#define FR(i,a,b) for(int i=(a);i<(b);++i)
#define FOR(i,n) FR(i,0,n)
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define A first
#define B second
#define mp(a,b) make_pair(a,b)
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef unsigned __int128 U128;
typedef __int128 I128;
typedef std::pair<int,int> PII;
typedef std::pair<LL,LL> PLL;
using namespace std;
//all ops have same strength
//once cur>=s[i], keeps going until win. get dist from n?
//while cur<s[i], keeps hopping....
//bsearch how many times it hops to get>=s[i]? at most 1e7
//store 2^ith parent -> p[layer][id]=node, gain in strength to get there
//what 2^ith parent is n?
/*
3
2 6 9
3 1 2
2 2 3
1 0 1
1
2 3
*/
LL n;
const LL MAXN=4e5+5, LOG=24;
LL p[MAXN][LOG][2][6]; //position, gain in strength. last number is layer
LL s[MAXN], w[MAXN];
LL d[MAXN]; //dist from n
LL lay[MAXN];
//when jump -> track when itll end up in next layer?
void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
n=(LL)N;
vector<LL> val;
FOR(i,n){
s[i]=(LL)S[i];
w[i]=(LL)W[i];
val.push_back(s[i]);
}
s[n]=(LL)1e9;
val.push_back(s[n]);
sort(val.begin(),val.end());
auto it=unique(val.begin(),val.end());
val.erase(it,val.end());
FOR(i,n+1){
lay[i]=lower_bound(val.begin(),val.end(),s[i])-val.begin();
}
FOR(layer,6){
FOR(i,n+1){
if (lay[i]!=layer){
p[i][j][0][layer]=i;
p[i][j][1][layer]=0;
}
else{
p[i][0][0][layer]=(LL)L[i];
p[i][0][1][layer]=(LL)P[i];
}
}
FR(j,1,LOG) FOR(i,n+1){
p[i][j][0][layer]=p[p[i][j-1][0][layer]][j-1][0][layer];
p[i][j][1][layer]=p[p[i][j-1][0][layer]][j-1][1][layer]+p[i][j-1][1][layer];
}
}
for (int i=n-1; i>=0; i--) d[i]=d[w[i]]+s[i];
return;
}
long long simulate(int X, int Z) {
LL x=(LL)X, z=(LL)Z;
LL cur=z, pos=x;
while (pos<n){
LL layer=lay[pos];
if (cur>=s[pos]) break;
LL lo=0, hi=(LL)(1e7+7);
while (lo<hi){
LL mid=(lo+hi)/2;
LL t=cur, pp=pos;
for (int j=0; j<LOG; j++){
if (mid&(1LL<<j)){
t+=p[pp][j][1][layer];
pp=p[pp][j][0][layer];
}
}
if (t>=s[pos] || lay[pp]>lay[pos]) hi=mid;
else lo=mid+1;
}
for (int j=0; j<LOG; j++){
if (lo&(1LL<<j)){
cur+=p[pos][j][1][layer];
pos=p[pos][j][0][layer];
}
}
//cout<<lo<<": "<<cur<<" "<<pos<<"\n";
}
cur+=d[pos];
return cur;
}
