#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{
int nxt,mini =inf,sum= 0;
};
const int mxbit = 30;
vector<vector<vector<node>>> lift;
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];
lift.resize(mxbit,vector<vector<node>>(20,vector<node>(n+1)));
vector<int> c(n+1,0);
for(int i = 0; i < n; i++)c[i]=p[i];
for(int b = 0;b < mxbit;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];
}
for(int bit = 0;bit <20;bit++)
lift[b][bit][n].nxt=n;
for(int bit=1;bit<20;bit++)
for(int i = 0; i < n; i++)
{
node x=lift[b][bit-1][i];
node y = lift[b][bit-1][x.nxt];
node&res = lift[b][bit][i];
res.nxt = y.nxt;
res.mini = min(x.mini,y.mini-x.sum);
res.sum = x.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 = lift[0][0].size();
n--;
for(int b = 0;b < mxbit&&x!=n;b++)
{
for(int bit = 19;bit >= 0;bit--)
{
node cur = lift[b][bit][x];
if((b==mxbit-1||cur.sum+z < (1ll<<b+1)) && cur.nxt!=n &&
(cur.mini-z>0))
x = cur.nxt,z+=cur.sum;
}
nxt(x,z);
}
return z;
}
#undef int
