#include "dungeons.h"
#include <cassert>
#include <cstring>
#include <algorithm>
#include <vector>
using ll = long long;
const int MN = 4e5+10;
const int W = 7; // 7 worlds
const int MUL = 16; // multiplier = 16
const int ML = 25; // 2^25 ~ 3e7
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
int N;
std::vector<int> s, p, w, l;
int jmp[W][MN][ML];
ll delta[W][MN][ML], max[W][MN][ML];
void init(int _N, std::vector<int> _s, std::vector<int> _p, std::vector<int> _w, std::vector<int> _l) {
N=_N;
s=_s, p=_p, w=_w, l=_l;
memset(jmp, -1, sizeof jmp);
int b=1;
for(int v=0;v<W;++v)
{
for(int i=0;i<N;++i)
if(s[i] < b)
{
jmp[v][i][0]=w[i];
delta[v][i][0]=s[i];
max[v][i][0]=INFL;
}
else
{
jmp[v][i][0]=l[i];
delta[v][i][0]=p[i];
max[v][i][0]=s[i]; // >= max -> unexpected; < max -> go ahead
}
for(int j=0;j+1<ML;++j)
for(int i=0;i<N;++i)
if(jmp[v][i][j]!=-1 && jmp[v][jmp[v][i][j]][j]!=-1)
{
int x = jmp[v][i][j];
jmp[v][i][j+1]=jmp[v][x][j];
delta[v][i][j+1]=delta[v][i][j]+delta[v][x][j];
max[v][i][j+1]=std::min(max[v][i][j], max[v][x][j]-delta[v][i][j]);
}
b *= MUL;
}
}
void step(int &n, ll &z)
{
if(n==N) return;
if(z<s[n])
z+=p[n], n=l[n];
else
z+=s[n], n=w[n];
}
void jump(int v, int cut, int &n, ll &z)
{
for(int i=ML-1;i>=0;--i)
if(jmp[v][n][i] != -1 && z<max[v][n][i] && (cut == -1 || z+delta[v][n][i]<cut)) // while isn't necessary here
z+=delta[v][n][i], n=jmp[v][n][i];
}
long long simulate(int n, int _z) {
ll z=_z;
int b=1;
for(int i=0;i+1<W;++i)
{
b *= MUL;
while(z<b)
{
jump(i, b, n, z);
step(n, z);
if(n==N) return z;
}
}
jump(W-1, -1, n, z);
assert(n==N);
return z;
}
