#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;
};
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];
vector<int> id(n);
for(int i = 0; i <n;i++)id[i]=i;
sort(id.begin(),id.end(),[&](int a,int b){return s[a]<s[b];});
lift.resize(25,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 <= 24;b++)
{
for(int i = 0; i <= n; i++)
{
lift[b][0][i].nxt = par[i],lift[b][0][i].sum = c[i];
if(i != n && __lg(s[i])==b)
lift[b][0][i].mini = i;
}
for(int bit = 1;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 = x.mini;
if(x.mini==inf||(y.mini!=inf&&s[x.mini]>s[y.mini]))
res.mini = y.mini;
res.sum = x.sum+y.sum;
}
for(int i = 0; i < n;i++)
if(__lg(s[id[i]])<=b)
par[id[i]] = w[id[i]],c[id[i]]=s[id[i]];
}
return;
}
long long simulate(signed _x, signed _z) {
int x = _x,z=_z;
int n = lift[0][0].size();
n--;
for(int b = 0;b <= 24,x!=n;b++)
{
for(int bit = 19;bit >= 0;bit--)
{
node cur = lift[b][bit][x];
if((cur.sum+z < (1<<b+1) || b == 24) && cur.nxt!=n &&
(cur.mini==inf ||stg[cur.mini]>cur.sum+z))
x = cur.nxt,z+=cur.sum;
}
if(z>=stg[x])
z+=stg[x],x = win[x];
else
z+=pen[x],x=lose[x];
}
return z;
}
#undef int
