#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;
int jump[N][32],lsum[N][32],f[N][32];
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 = 0;i<=n;i++) jump[i][0] = l[i],lsum[i][0] = p[i],f[i][0] = s[i];
for (int i=1;i<32;i++) {
for (int j = 0;j<=n;j++) {
jump[j][i] = jump[jump[j][i-1]][i-1];
lsum[j][i] = lsum[j][i-1]+lsum[jump[j][i-1]][i-1];
f[j][i] = min(f[j][i-1],f[jump[j][i-1]][i-1]-lsum[j][i-1]);
}
}
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]]+go[w[i]]-go[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]-go[i]});
}
}
fearsome[i].push_back({n,-1});
assert(big(fearsome[i]) <= 30);
}
}
int simulate(signed x, signed rz) {
int z = rz;
if (s[x] > z) {
for (int i = 31;i>=0;i--) {
if (f[x][i] <= z) continue;
z+=lsum[x][i];
x = jump[x][i];
}
}
while (1) {
int until = -1;
for (auto it : fearsome[x]) {
if (z < it.ss) {
until = it.ff;
break;
}
}
if (until == -1) {
z+=go[x];
break;
}
z+=go[x]-go[until];
x = until;
//f[node][i] --> node'dan itibaren 2^i hamle içinde kazanmak için minimum initial z
//f[node][i] = min(f[node][i-1],f[go[node][i]][i-1]-lsum[node][i])
//f[node][0] = s[node]
//lsum[node][0] = s[node], usual lift
for (int i = 31;i>=0;i--) {
if (f[x][i] <= z) continue;
z+=lsum[x][i];
x = jump[x][i];
}
}
return z;
}
