#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;
const int oth = 2e9;
struct node{
signed nxt;
signed mini =oth;
int sum= 0;
};
const int bv = 25;
const int mb = 16;
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(bv,vector<vector<node>>(mb,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 < 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 = oth;
}
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;
if(res.mini==oth&&y.mini==oth)
res.mini=oth;
else if(y.mini!=oth)
res.mini = max(-1ll,min((int)(res.mini),(int)(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 = lift[0][0].size();
n--;
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
