#include "dungeons.h"
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;
const int inf = 2e18;
struct node{
signed nxt;
int mini =inf,sum= 0;
};
const int bv = 25;
const int mb = 9;
node lift[9][25][400001];
vector<int> stg,win,lose,pen;
void init(signed _n, vector<signed> _s, vector<signed> _p, vector<signed> _w, vector<signed> _l) {
int n = _n;
vector<int> s(n),p(n),w(n),l(n);
for(int i = 0; i< n; i++)s[i]=_s[i],p[i]=_p[i],w[i]=_w[i],l[i]=_l[i];
stg = s;
win = w,lose = l,pen = p;
vector<int> par(n+1,n);
for(int i = 0; i < n; i++)
par[i] = l[i];
for(int i = 0; i < 9;i++)
for(int j =0;j<25;j++)
for(int k = 0; k <=n;k++)
lift[i][j][k] = node();
vector<int> c(n+1,0);
for(int i = 0; i < n; i++)c[i]=p[i];
for(int b = 0;b < bv;b++)
{
for(int i = 0; i < n; i++)
{
lift[b][0][i].nxt = par[i],lift[b][0][i].sum = c[i];
if(__lg(s[i])==b)
lift[b][0][i].mini = s[i];
else
lift[b][0][i].mini = inf;
}
for(int bit = 0;bit <mb;bit++)
lift[b][bit][n].nxt=n;
for(int bit=1;bit<mb;bit++)
for(int i = 0; i < n; i++)
{
node&res = lift[b][bit][i];
res = lift[b][bit-1][i];
for(int it = 0;it < (1<<((bv+mb-1)/mb))-1;it++)
{
node y = lift[b][bit-1][res.nxt];
res.nxt = lift[b][bit-1][res.nxt].nxt;
res.mini = min(res.mini,y.mini-res.sum);
res.sum+=y.sum;
}
}
for(int i = 0; i < n;i++)
if(__lg(s[i])<=b)
par[i] = w[i],c[i]=s[i];
}
return;
}
void nxt(int&x,int&z)
{
if(z>=stg[x])
z+=stg[x],x = win[x];
else
z+=pen[x],x=lose[x];
}
long long simulate(signed _x, signed _z) {
int x = _x,z=_z;
int n = stg.size();
for(int b = 0;b < bv&&x!=n;b++)
{
for(int bit = mb-1;bit >= 0;bit--)
{
node cur = lift[b][bit][x];
while((b==bv-1||cur.sum+z < (1ll<<b+1)) && cur.nxt!=n &&
(cur.mini>z))
x = cur.nxt,z+=cur.sum,cur = lift[b][bit][x];
}
nxt(x,z);
}
return z;
}
#undef int
