#include"dungeons.h"
#include<vector>
#include<iostream>
typedef long long ll;
using namespace std;
int n;
struct Dungeon{
vector<int>nxt1; // win
vector<int>nxt2; // lose
vector<int>st1; // strength
vector<int>st2; // gain on losing
vector<vector<int>>jmp; // where to jump?
vector<vector<ll>>gain; // strength gain of that jump
vector<vector<int>>win; // strength requirement to win in that jump
int pw;
ll thres=0;
Dungeon(int n):nxt1(n),nxt2(n),st1(n),st2(n){}
Dungeon()=default;
void setup(){
jmp=vector<vector<int>>((pw+1)/2,vector<int>(n+1));
gain=vector<vector<ll>>(n+1,vector<ll>((pw+1)/2));
win=vector<vector<int>>(n+1,vector<int>((pw+1)/2));
for(int p=0;p<pw;p++)
jmp[p/2][n]=n;
for(int i=0;i<n;i++){
jmp[0][i]=nxt2[i];
gain[i][0]=st2[i];
win[i][0]=st1[i];
}
for(int p=1;p<pw;p++){
for(int i=0;i<n;i++){
gain[i][p/2]=gain[i][(p-1)/2]+gain[jmp[(p-1)/2][i]][(p-1)/2];
if(win[jmp[(p-1)/2][i]][(p-1)/2]==1e9)
win[i][p/2]=win[i][(p-1)/2];
else
win[i][p/2]=max(0LL,min(1LL*win[i][(p-1)/2],1LL*win[jmp[(p-1)/2][i]][(p-1)/2]-gain[i][(p-1)/2]));
}
for(int i=0;i<n;i++)
jmp[p/2][i]=jmp[(p-1)/2][jmp[(p-1)/2][i]];
}
}
// simulate until it either reaches n-th node, wins, or strength>=thres
pair<int,ll>simulate(int x,ll st){
for(int p=(pw-1)/2;p>=0;p--){
while(jmp[p][x]!=n&&(1LL*win[x][p]>st||win[x][p]==1e9)&&st+gain[x][p]<thres){
st+=gain[x][p];
x=jmp[p][x];
}
}
while(x!=n&&st<thres){
// do 1 more jump
if(st>=st1[x]&&st1[x]!=1e9){
st+=st1[x];
x=nxt1[x];
break;
}else{
st+=st2[x];
x=nxt2[x];
}
}
return{x,st};
}
};
Dungeon dun[25];
vector<int>s,p,w,l;
void init(int N,vector<int>S,vector<int>P,vector<int>W,vector<int>L){
s=S;
p=P;
w=W;
l=L;
n=N;
for(int pw=0;pw<25;pw++){
dun[pw]=Dungeon(n);
dun[pw].thres=2LL<<pw;
dun[pw].pw=pw+1;
for(int i=0;i<n;i++){
if(s[i]<=1<<pw){
dun[pw].nxt1[i]=0;
dun[pw].nxt2[i]=w[i];
dun[pw].st1[i]=1e9;
dun[pw].st2[i]=s[i];
}else if(s[i]>=2<<pw){
dun[pw].nxt1[i]=0;
dun[pw].nxt2[i]=l[i];
dun[pw].st1[i]=1e9;
dun[pw].st2[i]=p[i];
}else{
dun[pw].nxt1[i]=w[i];
dun[pw].nxt2[i]=l[i];
dun[pw].st1[i]=s[i];
dun[pw].st2[i]=p[i];
}
}
}
dun[24].thres=1e18;
for(int pw=9;pw<25;pw++)
dun[pw].setup();
}
ll simulate(int x,int z){
ll st=z;
while(x!=n&&st<(1<<9)){
// do 1 more jump
if(st>=s[x]&&s[x]!=1e9){
st+=s[x];
x=w[x];
}else{
st+=p[x];
x=l[x];
}
}
for(int p=9;p<25;p++){
while(x!=n&&st<2LL<<p){
auto r=dun[p].simulate(x,st);
x=r.first;
st=r.second;
}
}
return st;
}
