#include <bits/stdc++.h>
#include "dungeons.h"
#pragma GCC target ("popcnt")
using namespace std;
typedef long long ll;
const int C=5; //cutoff between naive jumping and building base-4 jumps
const int N=400001;
int n;
int s[N];
int p[N];
int w[N];
int l[N];
int jump[N][11-C][12];
ll boost[N][11-C][12];
int mn[N][11-C][12];
int won[N];
int to[N];
int pw[N];
ll end_boost[N];
const int inf=(1<<30);
const int lim=10000000;
int msb(ll a)
{
int b=63-__builtin_clzll(a);
return (b/2);
}
void build(int lvl)
{
for(int i=0;i<n;i++)
{
won[i]=(msb(s[i])<=lvl+C);
to[i]=(won[i]==1?w[i]:l[i]);
pw[i]=(won[i]==1?s[i]:p[i]);
}
won[n]=1; to[n]=n; pw[n]=0;
//j=0
for(int i=0;i<=n;i++)
{
jump[i][lvl][0]=to[i];
boost[i][lvl][0]=pw[i];
mn[i][lvl][0]=(won[i]==0?s[i]:inf);
}
//j>0
for(int j=1;j<12;j++)
{
for(int i=0;i<=n;i++)
{
int a=i;
ll b=0;
int m=inf;
for(int k=0;k<4;k++)
{
m=min(m,int(max(ll(0),mn[a][lvl][j-1]-b)));
b+=boost[a][lvl][j-1];
a=jump[a][lvl][j-1];
}
jump[i][lvl][j]=a;
boost[i][lvl][j]=b;
mn[i][lvl][j]=m;
}
}
}
void build_end()
{
end_boost[n]=0;
for(int i=n-1;i>=0;i--) end_boost[i]=s[i]+end_boost[w[i]];
}
void init(int tn,vector<int> ts,vector<int> tp,vector<int> tw,vector<int> tl)
{
n=tn;
for(int i=0;i<n;i++){s[i]=ts[i]; p[i]=tp[i]; w[i]=tw[i]; l[i]=tl[i];}
for(int i=0;i<=10-C;i++) build(i);
build_end();
}
ll simulate(int a,int z)
{
ll b=z;
auto mv=[&]()
{
if(b>=s[a])
{
b+=s[a];
a=w[a];
}
else
{
b+=p[a];
a=l[a];
}
};
while(b<=(1<<(2*(C+1)))-1)
{
mv();
if(a==n) return b;
}
while(a!=n)
{
int lvl=min(msb(b)-1,11)-C;
if(lvl==11-C) break;
while(a!=n&&min(msb(b)-1,11)-C==lvl)
{
for(int j=11;j>=0;j--)
{
for(int k=0;k<3;k++)
{
if(jump[a][lvl][j]!=n&&b<mn[a][lvl][j])
{
b+=boost[a][lvl][j];
a=jump[a][lvl][j];
}
}
}
mv();
}
}
b+=end_boost[a];
return b;
}
