#include "bits/stdc++.h"
using namespace std;
//#define int long long
#pragma GCC optimize("Ofast")
int K = 4;
array<long long,3> P[400001][14][14];
long long inf = 1e18 , N;
vector<long long> S , PP , W , L;
vector<long long> v;
void init(int n, vector<int> s, vector<int> p, vector<int> w,vector<int> l){
for(auto i:s)S.push_back(i);
for(auto i:p)PP.push_back(i);
for(auto i:w)W.push_back(i);
for(auto i:l)L.push_back(i);
int cnt = 0;N = n;
bool ss = 0;int cst = 0;
while(cst<=1e7){
cst*=4;
if(ss){
cst = max(cst,1);
}
//cout<<cst<<" "<<cnt<<endl;
v.push_back(cst);
ss = 1;
for(int i = 0;i<n;i++){
if(s[i]<=cst){
P[i][cnt][0] = {w[i],s[i],inf};
}else{
P[i][cnt][0] = {l[i],p[i],s[i]};
}
}
P[n][cnt][0] = {n,0,-inf};
for(int j = 1;j<14;j++){
for(int i = 0;i<=n;i++){
long long pos = i , sum = 0 , nah = inf;
for(int e = 0;e<K;e++){
nah = min(nah,P[pos][cnt][j-1][2]-sum);
sum += P[pos][cnt][j-1][1];
pos = P[pos][cnt][j-1][0];
}
P[i][cnt][j] = {pos,sum,nah};
}
}
cnt++;
}
}
long long simulate(int x, int z) {
long long sum = z;
int cnt = 0;
while(x!=N){
//if(cnt<1000)cout<<sum<<endl;
cnt++;
long long nah = lower_bound(v.begin(),v.end(),sum+1)-v.begin();
nah--;
if(nah>26){
return -1;
}
for(int i = 13;i>=0;i--){
for(int e = 0;e<K-1;e++){
if(P[x][nah][i][2]>sum){
sum+=P[x][nah][i][1];
x = P[x][nah][i][0];
}
}
}
if(x==N)break;
//cout<<sum<<" "<<x<<" "<<nah<<endl;
if(sum>=S[x]){
sum+=S[x];
x = W[x];
}else{
sum+=PP[x];
x = L[x];
}
}
//cout<<cnt<<endl;
return sum;
}
