#include "dungeons.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
const int N = 50010;
const int LOGN = 40;
const int LOGT = 40;
long long s[N], p[N], w[N], l[N];
struct Binary_Lifting{
struct Node{
int pai;
long long sum, val;
Node(){
pai = 0;
sum = 0;
val = 1e18;
}
} bin[N][LOGT][LOGN];
void build(int n){
for(int j = 0;j < LOGT;j++){
long long c = (1LL<<j);
for(int i = 0;i < n;i++){
if(s[i] >= c){
bin[i][j][0].pai = l[i];
bin[i][j][0].sum = p[i];
bin[i][j][0].val = s[i];
}
else{
bin[i][j][0].pai = w[i];
bin[i][j][0].sum = s[i];
bin[i][j][0].val = 1e18;
}
}
bin[n][j][0].pai = n;
for(int bit = 1;bit < LOGN;bit++){
for(int i = 0;i <= n;i++){
bin[i][j][bit].pai = bin[bin[i][j][bit-1].pai][j][bit-1].pai;
bin[i][j][bit].sum = bin[i][j][bit-1].sum + bin[bin[i][j][bit-1].pai][j][bit-1].sum;
bin[i][j][bit].val = min(bin[i][j][bit-1].val, bin[bin[i][j][bit-1].pai][j][bit-1].val - bin[i][j][bit-1].sum);
}
}
}
}
} bin;
void init(int n, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
for(int i = 0;i < n;i++){
s[i] = S[i];
p[i] = P[i];
w[i] = W[i];
l[i] = L[i];
}
bin.build(n);
return;
}
long long simulate(int x, int z) {
long long ans = z, at = x;
for(int j = 0;j < LOGT;j++){
long long c = (1LL << j);
for(int bit = LOGN-1;bit >= 0;bit--){
if(bin.bin[at][j][bit].val <= ans){
continue;
}
ans += bin.bin[at][j][bit].sum;
at = bin.bin[at][j][bit].pai;
}
}
return ans;
}
