#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulHamidHan
//Sani buyuk Osman Pasa Plevneden cikmam diyor.
#define author tolbi
#include<bits/stdc++.h>
using namespace std;
template<typename T> vector<int32_t> normalize(vector<T> &rt){vector<int32_t> arr(rt.size());for (int i = 0; i < rt.size(); i++){arr[i]=rt[i];}return arr;}
#define endl '\n'
#define int long long
#define vint(x) vector<int> x
#define cinarr(x) for (auto &it : x) cin>>it;
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
#define sortarr(x) sort(x.begin(), x.end())
#define sortrarr(x) sort(x.rbegin(), x.rend())
#define rev(x) reverse(x.begin(), x.end())
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define tol(bi) (1LL<<((int)(bi)))
#define lsb(x) (x&-x)
const int MOD = 1e9+7;
const int64_t INF = LONG_LONG_MAX;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
#include "dungeons.h"
vector<vector<int>> st;
vector<vector<int>> stc;
map<int,vector<vector<int>>> stm;
map<int,vector<vector<int>>> stcm;
vector<int32_t> s,p,w,l;
set<int> kum;
int n, LOG;
void init(int32_t _n, vector<int32_t> _s, vector<int32_t> _p, vector<int32_t> _w, vector<int32_t> _l) {
n=_n+1;
s=_s,p=_p,w=_w,l=_l;
LOG=30;
for (int i = 0; i < s.size(); ++i)
{
kum.insert(s[i]);
}
}
int sum(int a, int b){
if (b>=INF-a) return INF;
return a+b;
}
void construct(int val){
if (stm.count(val)) return;
st.resize(n,vector<int>(LOG));
stc.resize(n,vector<int>(LOG));
st[n-1][0]=-1;
stc[n-1][0]=23;
for (int i = 0; i < n-1; i++){
if (val>=s[i]){
st[i][0]=w[i];
stc[i][0]=s[i];
}
else {
st[i][0]=l[i];
stc[i][0]=p[i];
}
}
for (int bit = 1; bit < LOG; bit++){
for (int node = 0; node < n; node++){
if (st[node][bit-1]==-1) {
st[node][bit]=-1;
stc[node][bit]=23;
continue;
}
st[node][bit]=st[st[node][bit-1]][bit-1];
stc[node][bit]=sum(stc[node][bit-1],stc[st[node][bit-1]][bit-1]);
}
}
swap(stm[val],st);
swap(stcm[val],stc);
}
pair<int,int> kthpar(int node, int kal){
int cur = 0;
for (int bit = LOG-1; bit >= 0; bit--){
if (st[node][bit]==-1) continue;
if (kal!=-1 && stc[node][bit]>=kal) continue;
kal-=stc[node][bit];
cur+=stc[node][bit];
node=st[node][bit];
}
return {node,cur};
}
int64_t simulate(int32_t x, int32_t z) {
if (x==n-1) return z;
auto it = kum.lower_bound(z+1);
int kk = 0;
if (it!=kum.begin()){
it--;
kk=*it;
}
construct(kk);
swap(st,stm[kk]);
swap(stc,stcm[kk]);
pair<int,int> gt;
if (kum.lower_bound(z+1)==kum.end()){
gt = kthpar(x,-1);
}
else {
gt = kthpar(x,*kum.lower_bound(z+1)-z);
}
z+=gt.second;
x=gt.first;
if (gt.first!=n-1){
z+=stc[x][0];
x=st[x][0];
}
swap(st,stm[kk]);
swap(stc,stcm[kk]);
return simulate(x,z);
}
