#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][7];
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 < 7; i++) {
thresh = (1 << (4 * i));
vis = vis2 = vector<int>(n, 0);
rev = vector<vector<int>>(n);
for (int j = 0; j < n; j++) {
if (thresh >= s[j]) {
to[j][i].par = w[j];if (w[j] != n)rev[w[j]].push_back(j);
} else {
to[j][i].par = l[j];if (l[j] != n)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 (to[t][i].par == n || vis[to[t][i].par]) break;
t = to[t][i].par;
}
int rt = t;
to[t][i].jump = to[t][i].thresh = to[t][i].ad = -1; to[t][i].dep = 0;
if (to[t][i].par != n) {
int curthresh = inf;
int cursm = 0;
while (1) {
if (!vis[t]) break;
vis[t] = 0;
if (thresh < s[t]) {
curthresh = min(curthresh, s[t] - cursm);
}
cursm += thresh >= s[t] ? s[t] : p[t];
t = to[t][i].par;
}
to[t][i].jump = t; to[t][i].thresh = curthresh; to[t][i].ad = cursm;
}
vector<int> st; st.push_back(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 (t2 == rt) {
continue;
}
to[t2][i].dep = to[to[t2][i].par][i].dep + 1;
to[t2][i].thresh = thresh >= s[t2] ? inf : s[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[t2][i].par][i].jump][i].jump;
to[t2][i].thresh = min(to[t2][i].thresh, min(to[to[t2][i].par][i].thresh - to[t2][i].ad, to[to[to[t2][i].par][i].jump][i].thresh - to[to[t2][i].par][i].ad - to[t2][i].ad));
to[t2][i].ad += to[to[to[t2][i].par][i].jump][i].ad + to[to[t2][i].par][i].ad;
}
}
}
}
return;
}
long long simulate(int32_t xx, int32_t zz) {
int cur = 0;
int x = xx; int z = zz;
while (x != n) {
while (cur + 1 < 7 && z >= (1LL << (4 * (cur + 1)))) cur++;
if (z < to[x][cur].thresh) {
if (to[x][cur].jump == x) {
int k = (to[x][cur].thresh - z + to[x][cur].ad - 1) / to[x][cur].ad;
z += to[x][cur].ad * k;
} else {
z += to[x][cur].ad; x = to[x][cur].jump;
}
} else {
if (z >= s[x]) {
z += s[x]; x = w[x];
} else {
z += p[x]; x = l[x];
}
}
}
return z;
}
