#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
/*
you can only go to an l chain after moving at least once on a w chain at most 32 ish times
because of the doubling effect??? or maybe wrong
draw the graph structure separately for w and l
for w chains you keep going until z + Σs[u] < s[v]
for l chains you keep going until z + Σp[u] ≥ s[v]
*/
// struct SegTree {
// int n; vector<int> st;
// SegTree(int n = 0) : n(n), st(4*n, 0) {}
// int query(int i, int l, int r, int ql, int qr) {
// if (qr <= l || r <= ql) return
// }
// };
int n;
vi s,p,w,l;
vvi wchain, lchain; vi seen, lc, wc, lp, wp;
void init(int N, vi S, vi P, vi W, vi L) {
n=N,s=S,p=P,w=W,l=L;
seen.assign(n+1, 0);
lc.assign(n+1, 0);
wc.assign(n+1, 0);
lp.assign(n+1, 0);
wp.assign(n+1, 0);
for (int i = 0; i < n; i++) {
if (seen[i]) continue;
int id = wc[i] = wchain.size();
wp[i] = 0;
seen[i] = 1;
wchain.push_back(vi(1, i));
int u = w[i];
while (!seen[u] && u != n) {
seen[u] = 1; wc[u] = id; wp[u] = wchain.back().size();
wchain.back().push_back(u);
u = w[u];
}
}
seen.assign(n+1, 0);
for (int i = 0; i < n; i++) {
if (seen[i]) continue;
int id = lc[i] = lchain.size();
seen[i] = 1; lp[i] = 0;
lchain.push_back(vi(1, i));
int u = l[i];
while (!seen[u] && u != n) {
seen[u] = 1; lc[u] = id; lp[u] = lchain.back().size();
lchain.back().push_back(u);
u = w[u];
}
}
}
ll simulate(int x, int Z) {
ll z = Z;
while (x != n) {
if (z >= s[x]) {
int id = wc[x], pos = wp[x];
for (int i = pos; i < wchain[id].size(); i++) {
if (z < s[wchain[id][i]]) break;
z += s[wchain[id][i]]; x = w[x];
}
// z += s[x];
// x = w[x];
} else {
// int id = lc[x], pos = lp[x];
// for (int i = pos; i < lchain[id].size(); i++) {
// if (z >= s[lchain[id][i]]) break;
// z += p[lchain[id][i]]; x = l[x];
// }
z += p[x];
x = l[x];
}
}
return z;
}
