#include <bits/stdc++.h>
#include "dungeons.h"
#define f first
#define s second
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define vec vector
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
const int N=400'000+1;
const int lt=19;
const int c=6;
int up[N][c][lt];
int mn[N][c][lt];
int go[N][c][lt];
ll pode[N];
int ok=0;
int w[N],s[N],p[N],l[N];
int n;
vec<int> kek;
vec<int> ps;
void clever_init(){
int pw=32;
ps.pb(1);
while(ps.back()<=(1e7)) ps.pb(ps.back()*pw);
int lv=sz(ps);
for(int i=n;i>=0;i--){
pode[i]=pode[w[i]]+s[i];
}
// cout<<lv<<endl;
for(int j=0;j+1<lv;j++){
for(int i=0;i<=n;i++){
if(s[i]>ps[j]&&s[i]<=(ps[j+1])){
mn[i][j][0]=s[i];
go[i][j][0]=l[i];
up[i][j][0]=p[i];
}
else if(s[i]<=ps[j]){
go[i][j][0]=w[i];
up[i][j][0]=s[i];
mn[i][j][0]=1e9;
}
else{
go[i][j][0]=l[i];
up[i][j][0]=p[i];
mn[i][j][0]=1e9;
}
}
for(int st=1;st<lt;st++){
for(int i=0;i<=n;i++){
mn[i][j][st]=min(mn[i][j][st-1],mn[go[i][j][st-1]][j][st-1]-up[i][j][st-1]);
go[i][j][st]=go[go[i][j][st-1]][j][st-1];
up[i][j][st]=min(ps.back(),up[i][j][st-1]+up[go[i][j][st-1]][j][st-1]);
}
}
}
}
ll clever_query(int x,int z){
ll sm=z;
int t=upper_bound(all(ps),sm)-ps.begin()-1;
while(sm<kek.back() && x!=n){
while(sm>=(ps[t+1])) ++t;
for(int j=lt-1;j>=0;j--){
if(mn[x][t][j]>sm && (sm+up[x][t][j])<=kek.back() && (sm+up[x][t][j])<(ps[t+1])){
sm+=up[x][t][j];
x=go[x][t][j];
}
}
if(sm<s[x]){
sm+=p[x];
x=l[x];
}
else{
sm+=s[x];
x=w[x];
}
}
if(x!=n) assert(sm>=kek.back());
sm+=pode[x];
return sm;
}
void init(int n, vec<int> a,vec<int> b,vec<int> c,vec<int> d){
for(int i=0;i<n;i++){
s[i]=a[i];
p[i]=b[i];
w[i]=c[i];
l[i]=d[i];
}
s[n]=0;w[n]=n;l[n]=n;p[n]=0;
::n=n;
for(int i=0;i<n;i++) kek.pb(s[i]);
sort(all(kek));kek.erase(unique(all(kek)),kek.end());
clever_init();
}
long long simulate(int x, int z){
return clever_query(x,z);
}
/*
3 2
13 13 13
4 3 1
2 2 3
1 0 1
0 1
2 3
*/
