#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 = 1e9;
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();
if(flag) {
Key = 0;
return;
}
flag = 1;
for(int i = 0; i < n; i++) flag &= (s[i] == s[0]);
if(flag) {
Key = 1;
sub3::build();
return;
}
}
long long brute(int x, int z1) {
ll z = z1;
flag = 0;
return recur(x, z);
}
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);
}
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
/*
5 1000
26 26 26 26 26
44 12 31 9 41
3 2 5 4 5
3 2 5 3 3
3 22
*/
vector<int> s1(n), p1(n), w1(n), l1(n);
int q;
void gen() {
n = 100; q = 1000;
s1.resize(n);
s1[0] = rnd() % 1000000;
for(int i = 0; i < n; i++)
s1[i] = s1[0];
p1.resize(n);
for(int i = 0; i < n; i++)
p1[i] = rnd() % 1000000;
w1.resize(n);
for(int i = 0; i < n; i++)
w1[i] = rnd() % (n - i) + i + 1;
l1.resize(n);
for(int i = 0; i < n; i++)
l1[i] = rnd() % n;
}
// int main() {
// cin >> n >> q;
// s1.resize(n);
// p1.resize(n);
// w1.resize(n);
// l1.resize(n);
// for(int &c : s1)
// cin >> c;
// for(int &c : p1)
// cin >> c;
// for(int &c : w1)
// cin >> c;
// for(int &c : l1)
// cin >> c;
// init(n, s1, p1, w1, l1);
// while(q--) {
// int x, y;
// cin >> x >> y;
// cout << simulate(x, y) << '\n';
// }
// for(int t = 0; t < 100; t++) {
// gen();
// init(n, s1, p1, w1, l1);
// while(q--) {
// int x = rnd() % n, z = rnd() % 1000;
// // if(brute(x, z) == -1) {
// // cout << "Wrong observation :(\n";
// // cout << n << '\n';
// // for(int c : s1) cout << c << ' ';
// // cout << '\n';
// // for(int c : p1) cout << c << ' ';
// // cout << '\n';
// // for(int c : w1) cout << c << ' ';
// // cout << '\n';
// // for(int c : l1) cout << c << ' ';
// // cout << '\n';
// // cout << x << ' ' << z;
// // exit(0);
// // }
// // if(brute(x, z) != simulate(x, z)) {
// // cout << "WA\n";
// // cout << x << ' ' << z << '\n';
// // cout << "expexted: " << brute(x, z) << '\n';
// // cout << "found: " << simulate(x, z) << '\n';
// // return 0;
// // }
// }
// }
// cout << "OK";
// }
