#include <bits/stdc++.h>
using namespace std;
#include "dungeons.h"
#define int long long
vector<vector<tuple<int,int,int>>> lose,win;
vector<int> skip;
int m;
void init(signed n,vector<signed> s,vector<signed> p,vector<signed> w,vector<signed> l){
m = n;
lose = vector(n+1,vector<tuple<int,int,int>>(24));
for (int i(0);i < n;++i) lose[i][0] = make_tuple(l[i],s[i],p[i]);
lose[n][0] = make_tuple(n,0,0);
for (int k(1);k < 24;++k) for (int i(0);i <= n;++i){
auto [a,b,c] = lose[i][k-1]; auto [d,e,f] = lose[a][k-1];
lose[i][k] = make_tuple(d,min(b,e-c),c+f);
}
win = vector(n+1,vector<tuple<int,int,int>>(24));
for (int i(0);i < n;++i) win[i][0] = make_tuple(w[i],s[i],s[i]);
win[n][0] = make_tuple(n,1e18,0);
for (int k(1);k < 24;++k) for (int i(0);i <= n;++i){
auto [a,b,c] = win[i][k-1]; auto [d,e,f] = win[a][k-1];
win[i][k] = make_tuple(d,max(b,e-c),c+f);
}
skip = vector<int>(n+1);
for (int i(n-1);i > -1;--i) skip[i] = skip[w[i]]+s[i];
}
int simulate(signed x,signed y){
int z = y,t = 0;
while(x!=m&&z<1e7){
++t;
if (get<1>(win[x][0])>z){
for (int l(23);l > -1;--l) if (get<1>(lose[x][l])>z){
z += get<2>(lose[x][l]),x = get<0>(lose[x][l]);
}
} else {
for (int l(23);l > -1;--l) if (get<1>(win[x][l])<=z){
z += get<2>(win[x][l]),x = get<0>(win[x][l]);
}
}
}
return z+skip[x];
}
