#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 10 , Sq = 3000 , B = N / Sq + 2 , inf = 1e7 , Lg = 27;
int n , nex[N] , pos[N][Lg];
long long dis[N] , val[N] , sum[N][Lg] , best[N][Lg];
vector <int> s , p , w , l;
void init(int nn, vector<int> ss, vector<int> pp, vector<int> ww, vector<int> ll) {
n = nn;
s = ss;
p = pp;
w = ww;
l = ll;
dis[n] = 0;
nex[n] = n;
l.push_back(n);
w.push_back(n);
p.push_back(0);
s.push_back(0);
for(int i = n - 1 ; i >= 0 ; i--)
{
dis[i] = dis[w[i]] + s[i];
if(s[i] >= Sq)
{
nex[i] = i;
val[i] = 0;
}
else
{
nex[i] = nex[w[i]];
val[i] = s[i] + val[w[i]];
}
}
for(int i = 0 ; i <= n ; i++)
{
sum[i][0] = p[i] + val[l[i]];
pos[i][0] = nex[l[i]];
best[i][0] = s[pos[i][0]] - sum[i][0];
}
for(int j = 1 ; j < Lg ; j++)
{
for(int i = 0 ; i <= n ; i++)
{
sum[i][j] = sum[i][j - 1] + sum[pos[i][j - 1]][j - 1];
pos[i][j] = pos[pos[i][j - 1]][j - 1];
best[i][j] = min(best[i][j - 1] , best[pos[i][j - 1]][j - 1] - sum[i][j]);
}
}
return;
}
long long simulate(int x, int zz) {
long long z = zz;
while(z < Sq && x != n)
{
if(z >= s[x])
{
z += s[x];
x = w[x];
}
else
{
z += p[x];
x = l[x];
}
}
if(x == n)
return z;
while(z < inf)
{
z += val[x];
x = nex[x];
if(x == n)
break;
if(z >= s[x])
{
z += s[x];
x = w[x];
}
else
{
for(int i = Lg - 1 ; i >= 0 ; i--)
{
if(best[x][i] > z)
{
z += sum[x][i];
x = pos[x][i];
}
}
z += p[x];
x = l[x];
}
}
z += dis[x];
return z;
}
