#include<bits/stdc++.h>
#include "dungeons.h"
using namespace std;
using ll = long long;
int n;
vector<int> s, p, w, l;
bool flag = 0;
ll recur(int cur, ll &val) {
if(cur == n) return val;
if(val >= s[cur]) {
flag = 1;
return recur(w[cur], val += s[cur]);
}
if(flag) return -1;
flag = 0;
return recur(l[cur], val += p[cur]);
}
namespace sub2 {
const int N = 400010;
vector<int> g[N];
int anc[N][19];
ll bl[N][19], sum[N];
void dfs(int cur, int p) {
anc[cur][0] = p;
for(int i = 1; i < 19; i++)
anc[cur][i] = anc[anc[cur][i - 1]][i - 1];
if(cur != n) {
bl[cur][0] = s[cur] + sum[cur];
for(int i = 1; i < 19; i++)
bl[cur][i] = max(bl[cur][i - 1], bl[anc[cur][i - 1]][i - 1]);
}
for(int to : g[cur]) {
sum[to] = sum[cur] + s[to];
dfs(to, cur);
}
}
int find(int x, ll val) {
val += sum[x];
for(int i = 18; i >= 0; i--) {
if(val >= bl[x][i])
x = anc[x][i];
}
return x;
}
void build() {
for(int i = 0; i < n; i++) {
g[w[i]].push_back(i);
}
sum[0] = 0;
dfs(n, n);
for(int i = 0; i < n; i++) g[i].clear();
}
};
namespace sub3 {
const int N = 50010;
const ll INF = 1e8;
ll bl[N][24];
int to[N][24];
void build() {
for(int lev = 0; lev < 24; lev++) {
bl[n][lev] = INF;
to[n][lev] = n;
for(int i = 0; i < n; i++) {
if(!lev) {
bl[i][lev] = p[i];
to[i][lev] = l[i];
}
else {
bl[i][lev] = min(bl[i][lev - 1] + bl[to[i][lev - 1]][lev - 1], INF);
to[i][lev] = to[to[i][lev - 1]][lev - 1];
}
}
}
}
};
int Key = -1;
void init(int N, vector<int> s1, vector<int> p1, vector<int> w1, vector<int> l1) {
n = N; s = s1; p = p1; w = w1; l = l1;
bool flag = 1;
for(int i = 0; i < n; i++)
flag &= (s[i] == p[i]);
sub2::build();
sub3::build();
Key = 1;
}
long long simulate(int x, int z1) {
ll z = z1;
if(Key == 0) {
while(x != n) {
int next = sub2::find(x, z);
z += sub2::sum[x] - sub2::sum[next];
x = next;
if(x == n) break;
z += p[x];
x = l[x];
}
return z;
}
if(Key == 1) {
for(int i = 23; i >= 0; i--) {
if(z + sub3::bl[x][i] < s[0]) {
z += sub3::bl[x][i];
x = sub3::to[x][i];
}
}
if(z < s[0])
z += p[x],
x = l[x];
return z + sub2::sum[x];
}
return recur(x, z);
}
