#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 1e15;
int n; vector<int32_t> s, p, w, l;
const int mx = 4e5 + 5;
struct uwu {
int jump;
int thresh;
int ad;
int dep;
int par;
} to[mx][25];
const int x = sizeof(to);
vector<vector<int>> rev;
vector<int> vis, vis2;
int thresh;
void init(int32_t nn, std::vector<int32_t> ss, std::vector<int32_t> pp, std::vector<int32_t> ww, std::vector<int32_t> ll) {
n = nn; s = ss; p = pp; w = ww; l = ll;
for (int i = 0; i < 25; i++) {
thresh = (1 << i);
vis = vis2 = vector<int>(n, 0);
rev = vector<vector<int>>(n);
for (int j = 0; j < n; j++) {
if (w[j] != n && thresh > s[j]) rev[w[j]].push_back(j);
else rev[l[j]].push_back(j);
}
for (int j = 0; j < n; j++) {
if (vis2[j]) continue;
int t = j;
while (1) {
vis[t] = 1;
if (thresh >= s[t]) {
to[t][i].par = w[t];
if (w[t] == n || vis[w[t]]) break;
t = w[t];
} else {
to[t][i].par = l[t];
if (vis[l[t]]) break;
t = l[t];
}
}
vector<int> st; st.push_back(t);
int rt = t;
while (!st.empty()) {
int t2 = st.back(); st.pop_back();
if (vis2[t2]) continue;
vis2[t2] = 1; for (auto& x : rev[t2]) st.push_back(x);
if (t == rt) {
to[t2][i].jump = to[t2][i].thresh = to[t2][i].ad = -1; to[t2][i].dep = 0;
continue;
}
to[t2][i].dep = to[to[t2][i].par][i].dep + 1;
to[t2][i].thresh = thresh >= s[t2] ? inf : p[t2];
to[t2][i].ad = thresh >= s[t2] ? s[t2] : p[t2];
to[t2][i].jump = to[t2][i].par;
if (rt == to[t2][i].par) {
} else if (rt == to[to[t2][i].par][i].jump) {
} else if (to[to[to[t2][i].par][i].jump][i].dep - to[to[t2][i].par][i].dep == to[to[to[to[t2][i].par][i].jump][i].jump][i].dep - to[to[to[t2][i].par][i].jump][i].dep) {
to[t2][i].jump = to[to[to[to[t2][i].par][i].jump][i].jump][i].dep;
to[t2][i].thresh = min(to[t2][i].thresh, min(to[to[to[t2][i].par][i].jump][i].thresh - to[t2][i].ad, to[to[to[to[t2][i].par][i].jump][i].jump][i].thresh - to[to[to[t2][i].par][i].jump][i].ad - to[t2][i].ad));
to[t2][i].ad += to[to[to[to[t2][i].par][i].jump][i].jump][i].ad + to[to[to[t2][i].par][i].jump][i].ad;
}
}
}
}
return;
}
long long simulate(int32_t x, int32_t z) {
int cur = 0;
while (x != n) {
while (cur + 1 < 25 && z >= (1LL << (cur + 1))) cur++;
if (z <= to[x][cur].thresh) { z += to[x][cur].ad; x = to[x][cur].jump; } else {
if (z >= s[x]) {
z += s[x]; x = w[x];
} else {
x = l[x];
}
}
}
return z;
}
