#include <bits/stdc++.h>
using namespace std;
#include "dungeons.h"
constexpr int m = 3;
array<vector<array<tuple<int,long long,long long>,24>>,(25+m-1)/m> table;
vector<int> E;
void init(int n,vector<int> A,vector<int> C,vector<int> B,vector<int> D){
E = B;
for (int i(0);i < (25+m-1)/m;++i){
auto& tbl = table[i]; tbl.resize(n+1);
tbl[n][0] = make_tuple(n,1e18,0);
for (int k(0);k < n;++k){
if (A[k]<=(1<<m*i)) tbl[k][0] = make_tuple(B[k],1e18,A[k]);
else tbl[k][0] = make_tuple(D[k],A[k],C[k]);
}
for (int j(1);j < 24;++j) for (int k(0);k <= n;++k){
auto [a,b,c] = tbl[k][j-1]; auto [d,e,f] = tbl[a][j-1];
tbl[k][j] = make_tuple(d,min(b,e-c),c+f);
}
}
}
long long simulate(int x,int Y){
int n = E.size();
long long y(Y);
for (int i(0);i < (25+m-1)/m;++i) while((1<<m*i)<=y&&y<(1<<m*(i+1))){
auto& tbl = table[i];
for (int l(23);l > -1;--l) if (get<0>(tbl[x][l])!=n&&get<1>(tbl[x][l])>y){
y += get<2>(tbl[x][l]),x = get<0>(tbl[x][l]);
}
if (get<1>(tbl[x][0])>y&&get<0>(tbl[x][0])==n) return y+get<2>(tbl[x][0]);
y += get<1>(tbl[x][0]),x = E[x];
if (x==n) return y;
}
auto& tbl = table[24];
for (int l(23);l > -1;--l) if (get<0>(tbl[x][l])!=n){
y += get<2>(tbl[x][l]),x = get<0>(tbl[x][l]);
}
return y+get<2>(tbl[x][0]);
}
