#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)
constexpr int mxN = 400005, LOG = 30;
vt<int> S, P, W, L;
int N, subtask;
int tree_lift[mxN][LOG+1];
ll tree_lift_val[mxN][LOG+1];
ll depth[mxN];
vt<int> vals;
int lift[5][mxN][LOG+1];
ll lift_val[5][mxN][LOG+1];
ll simulate(int i, int zz) {
ll z = zz;
if (subtask == 4) {
FOR(x, 0, size(vals)-1) {
ROF(j, LOG, 0)
if (z + lift_val[x][i][j] < vals[x]) {
z += lift_val[x][i][j];
i = lift[x][i][j];
}
if (z < vals[x]) {
if (z < S[i]) {
z += P[i];
i = L[i];
} else {
z += S[i];
i = W[i];
}
}
}
return z + depth[i] - depth[N];
}
while (i != N) {
int cur = i;
ROF(j, LOG, 0)
if (depth[i] + z >= tree_lift_val[cur][j])
cur = tree_lift[cur][j];
z += depth[i] - depth[cur] + P[cur];
i = L[cur];
}
return z;
/*
while (i != N) {
if (z < S[i]) {
z += P[i];
i = L[i];
} else {
z += S[i];
i = W[i];
}
}
return z;
*/
}
void init(int _N, vt<int> _S, vt<int> _P, vt<int> _W, vt<int> _L) {
N = _N, S = _S, P = _P, W = _W, L = _L;
bool sub2 = true;
FOR(i, 0, N-1)
sub2 &= S[i] == P[i];
S.push_back(0);
P.push_back(0);
W.push_back(N);
L.push_back(N);
ROF(i, N, 0) {
depth[i] = depth[W[i]] + S[i];
tree_lift[i][0] = W[i];
tree_lift_val[i][0] = S[i] + depth[i];
}
if (sub2) {
subtask = 2;
FOR(j, 1, LOG)
FOR(i, 0, N) {
tree_lift[i][j] = tree_lift[tree_lift[i][j-1]][j-1];
tree_lift_val[i][j] = max(tree_lift_val[tree_lift[i][j-1]][j-1], tree_lift_val[i][j-1]);
}
#ifdef DEBUG
cout << "subtask = 2\n";
#endif
return;
}
vals = S;
sort(all(vals));
vals.erase(unique(all(vals)), vals.end());
if (size(vals) <= 5) {
subtask = 4;
FOR(x, 0, size(vals)-1) {
FOR(i, 0, N) {
if (S[i] >= vals[x]) {
lift[x][i][0] = L[i];
lift_val[x][i][0] = P[i];
} else {
lift[x][i][0] = W[i];
lift_val[x][i][0] = S[i];
}
}
FOR(j, 1, LOG)
FOR(i, 0, N) {
lift[x][i][j] = lift[x][lift[x][i][j-1]][j-1];
lift_val[x][i][j] = lift_val[x][lift[x][i][j-1]][j-1] + lift_val[x][i][j-1];
}
}
#ifdef DEBUG
cout << "subtask = 4\n";
#endif
return;
}
#ifdef DEBUG
cout << "subtask = 1\n";
#endif
}
