#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vi>;
using vvll = vector<vll>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using ui = unsigned int;
using ull = unsigned long long;
using pui = pair<ui,ui>;
using pull = pair<ull,ull>;
template<typename T>
using vc = std::vector<T>;
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define yes cout << "yes\n"
#define no cout << "no\n"
#define Yes cout << "Yes\n"
#define No cout << "No\n"
template<typename T> void sc(T &x) { cin >> x; }
template<typename T, typename U> void sc(pair<T,U> &p) { sc(p.first), sc(p.second); }
template<typename T> void sc(vector<T> &v) { for (auto &x : v) sc(x); }
template<typename... A> void sc(A&... a) { (sc(a), ...); }
template<typename T> void _pt(const T &x){cout << x;}
template<typename T, typename U> void _pt(const pair<T,U> &p){_pt(p.first); cout << ' '; _pt(p.second);}
template<typename T> void _pt(const vector<T> &v){bool f=1; for(auto &x:v){if(!f) cout<<' '; _pt(x); f=0;}}
template<typename... A> void pt(const A&... a){(_pt(a), ...);}
template<typename T, typename U> bool umin(T &a, const U &b) { return b < a ? (a = b, true) : false; }
template<typename T, typename U> bool umax(T &a, const U &b) { return b > a ? (a = b, true) : false; }
#define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define FOR1(n) for (int i=0; i<(n); ++i)
#define FOR2(i,n) for (int i=0; i<(n); ++i)
#define FOR3(i,l,r) for (int i=(l); i<(r); ++i)
#define FOR4(i,l,r,k) for (int i=(l); i<(r); i+=(k))
#define FOR(...) GET_MACRO(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define ROF1(n) for (int i=(n)-1; i>=0; --i)
#define ROF2(i,n) for (int i=(n)-1; i>=0; --i)
#define ROF3(i,l,r) for (int i=(r)-1; i>=(l); --i)
#define ROF4(i,l,r,k) for (int i=(r)-1; i>=(l); i-=(k))
#define ROF(...) GET_MACRO(__VA_ARGS__, ROF4, ROF3, ROF2, ROF1)(__VA_ARGS__)
#define all(c) (c).begin(), (c).end()
#define allr(c) (c).rbegin(), (c).rend()
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define trav(x,a) for (auto &x : (a))
#define sz(a) ((int)(a).size())
#define mem(a,v) memset(a, v, sizeof(a))
#define nl pt("\n")
#include "dungeons.h"
int n;
vi s, p, w, l;
int maxs = 1;
using pil = pair<int, ll>;
vc<vc<pil>> toNext;
const ll inf = 4e18;
void init(int _n, vi _s, vi _p, vi _w, vi _l) {
n = _n;
s = _s;
p = _p;
w = _w;
l = _l;
maxs = *max_element(all(s));
int B = max(1, (int)sqrt(n));
toNext.assign(n, vc<pil>(maxs + 1, {0, 0}));
FOR(L, 0, n, B) {
int R = min(n - 1, L + B - 1);
ROF(i, L, R + 1) {
ROF(z, 1, maxs + 1) {
if(z >= s[i]) {
int nxt = w[i];
ll val = (ll)z + (ll)s[i];
toNext[i][z] = {nxt, val};
}
else {
int nxt = l[i];
ll val = (ll)z + (ll)p[i];
while(nxt <= R) {
if(val > maxs) {
auto pr = toNext[nxt][maxs];
nxt = pr.fi;
val = pr.se + (val - maxs);
}
else {
auto pr = toNext[nxt][(int)val];
nxt = pr.fi;
val = pr.se;
}
}
toNext[i][z] = {nxt, val};
}
}
}
}
}
ll simulate(int x, int Z) {
ll z = Z;
int cur = x;
ll curStart = z;
while(cur != n) {
pil pr;
if(curStart > maxs)
pr = toNext[cur][maxs];
else
pr = toNext[cur][(int)curStart];
int nxt = pr.fi;
ll val = pr.se;
cur = nxt;
curStart = val;
}
return curStart;
}
// int32_t main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// init(3, {2, 6, 9}, {3, 1, 2}, {2, 2, 3}, {1, 0, 1});
// pt(simulate(0, 1)); nl;
// pt(simulate(2, 3)); nl;
// return 0;
// }
