#include "dungeons.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9;
//a node'unda kazanıyorsam ama b'nodeunda kaybediyosam s[a]*2 < s[b] olmalı
//fonksiyonel graf şeklinde kaybedicem
//ilk kez kazanınca nerde olcağımı ve gücümü hesaplamak casework ile O(1)
//binary lifting?
//z+l[node]+l[w[node]]... >= s[w[w[...node]]]
//kaç kez kaybedebilirim?
//s[i]/p[i]+1 kez olabilir l[i] = i ise
//kaybettiğim bir adamı yenersem gücüm iki katıma çıkar
//sürekli ilk kaybedeceğim yeri bulayım (25 candidate var)
//fonksiyonal grafa göre ordan ilk kazanacağım yeri bulayım
//Q*R*(25+log(N))
//repeat
//51+11? puan alır
//13 because ilk kez kazanınca kaybetmicem
//12 because 5 kez kazanınca kaybetmicem
//26 because her durumda 2 katına çıkıyorum
//Bir yerde z güçle ne zaman kaybedicem
//first t s.t z+p[node][t] < go[node][t]-s[node][t]
//herkes için
const int N = 400001;
vector<pii> fearsome[N];
vi s,p,w,l;
vi go(N,0);
int n;
void init(signed nn, std::vector<signed> S, std::vector<signed> P, std::vector<signed> W, std::vector<signed> L) {
//bi sonrakini yenemiyosam bi sonraki + onunkiler (s[i]*2 < s[nxt])
//yeniyosam alıp onunkilerden poplicam
w = vi(all(W)),s = vi(all(S)),p = vi(all(P)),l = vi(all(L));
n = nn;
s.push_back(0);
p.push_back(0);
w.push_back(n);
l.push_back(n);
for (int i = n;i>=0;i--) go[i] = go[w[i]]+s[i];
//s[i]+(s[i]+s[w[i]]+s[w[w[i]]]...) < s[t]
//s[i]+go[i]-go[t] < s[t] --> s[i]+go[i] < s[t]+go[t]
for (int i = n-1;i>=0;i--) {
if (s[i]+go[i] < s[w[i]]+go[w[i]]) fearsome[i].push_back({w[i],s[w[i]]-s[i]});
for (auto it : fearsome[w[i]]) {
if (go[it.ff]+s[it.ff] > s[i]+go[i]) {
fearsome[i].push_back({it.ff,s[it.ff]+go[it.ff]-s[i]-go[i]});
}
}
fearsome[i].push_back({n,-1});
assert(big(fearsome[i]) <= 30);
}
}
int simulate(signed x, signed rz) {
int z = rz;
while (z < s[x]) {
//cerr << "LOSE" sp x sp z << '\n';
z += p[x];
x = l[x];
}
while (1) {
int until = x;
for (auto it : fearsome[x]) {
//cerr << "FEAR" sp it.ff sp it.ss << '\n';
if (z < it.ss) break;
//cerr << "BEATEN\n";
until = it.ff;
}
z+=go[x]-go[until]+s[until];
if (until == n) break;
x = w[until];
while (z < s[x]) {
//cerr << "LOSE" sp x sp z << '\n';
z += p[x];
x = l[x];
}
}
return z;
}
