#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] => Σs[u] - s[v] < -z
for l chains you keep going until z + Σp[u] ≥ s[v] => s[v] - Σp[u] ≤ z
*/
struct SegTree {
int n; vector<int> st;
SegTree(int n = 0) : n(n), st(4*n, 1e9) {}
int query(int i, int l, int r, int ql, int qr) {
if (qr <= l || r <= ql) return 1e9;
if (ql <= l && r <= qr) return st[i];
int m = l + (r-l) / 2;
return min(query(2*i+1,l,m,ql,qr),query(2*i+2,m,r,ql,qr));
}
int update(int i, int l, int r, int k, int v) {
if (!(l <= k && k < r)) return st[i];
if (l + 1 == r) return st[i] = v;
int m = l + (r-l) / 2;
return st[i] = min(update(2*i+1,l,m,k,v),update(2*i+2,m,r,k,v));
}
int query(int l, int r) {
return query(0,0,n,l,r+1);
}
void update(int k, int v) {
update(0,0,n,k,v);
}
};
int n;
vi s,p,w,l;
vvi wchain, lchain, wsum, lsum; vi seen, lc, wc, lp, wp;
vector<SegTree> wst, lst;
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);
auto process = [](int n, vi &w, vi &seen, vi &wc, vi &wp, vvi &wchain, vvi &wsum, vector<SegTree> &wst) {
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));
wsum.push_back(vi(1, 0));
int running = s[i];
vi values(1, -s[i]);
int u = w[i];
while (!seen[u] && u != n) {
wsum.back().push_back(running);
values.push_back(running - s[u]);
seen[u] = 1; wc[u] = id; wp[u] = wchain.back().size();
wchain.back().push_back(u);
running += s[u];
u = w[u];
}
wst.push_back(SegTree(values.size()));
for (int i = 0; i < values.size(); i++) wst.back().update(i, values[i]);
}
};
seen.assign(n+1, 0);
process(n, w, seen, wc, wp, wchain, wsum, wst);
seen.assign(n+1, 0);
process(n, l, seen, lc, lp, lchain, lsum, lst);
}
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;
}
