#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 400001;
const int LOG = 35;
vector<vector<long long>> distW, nxtW, miniW, distL, nxtL, miniL;
vector<int> s,p,w,l;
int n;
void init(int nn, vector<int> ss, vector<int> pp, vector<int> ww, vector<int> ll) {
ios::sync_with_stdio(false);
cin.tie(0);
s = ss; p = pp; w = ww; l = ll; n = nn;
l.push_back(n); p.push_back(0); s.push_back(0); w.push_back(n);
distW.resize(MAX_N, vector<long long>(LOG));
nxtW.resize(MAX_N, vector<long long>(LOG));
miniW.resize(MAX_N, vector<long long>(LOG));
distL.resize(MAX_N, vector<long long>(LOG));
nxtL.resize(MAX_N, vector<long long>(LOG));
miniL.resize(MAX_N, vector<long long>(LOG));
for (int j = 0; j <= n; j++) {
distW[j][0] = s[j];
nxtW[j][0] = w[j];
miniW[j][0] = s[w[j]] - s[j];
distL[j][0] = p[j];
nxtL[j][0] = l[j];
miniL[j][0] = s[l[j]] - p[j];
}
for (int k = 1; k < LOG; k++){
for (int j = 0; j <= n; j++) {
distW[j][k] = distW[j][k-1] + distW[nxtW[j][k-1]][k-1];
nxtW[j][k] = nxtW[nxtW[j][k-1]][k-1];
miniW[j][k] = max(miniW[j][k-1], miniW[nxtW[j][k-1]][k-1] - distW[j][k-1]);
distL[j][k] = distL[j][k-1] + distL[nxtL[j][k-1]][k-1];
nxtL[j][k] = nxtL[nxtL[j][k-1]][k-1];
miniL[j][k] = min(miniL[j][k-1], miniL[nxtL[j][k-1]][k-1] - distL[j][k-1]);
}
}
}
long long simulate(int x, int z) {
long long st = z;
int pos = x;
while (pos != n) {
if (st < s[pos]) {
for (int i = LOG-1; i >= 0; i--) {
if (st >= miniL[pos][i]) continue;
st += distL[pos][i];
pos = nxtL[pos][i];
}
st += p[pos];
pos = l[pos];
cerr << pos << ' ' << st << '\n';
}
else {
for (int i = LOG-1; i >= 0; i--) {
if (st < miniW[pos][i]) continue;
st += distW[pos][i];
pos = nxtW[pos][i];
}
st += s[pos];
pos = w[pos];
}
}
return st;
}
