#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 5e4;
const ll INF = 1e18;
int N;
int S[MAXN+10], P[MAXN+10], W[MAXN+10], L[MAXN+10];
ll A[MAXN+10][30][30], B[MAXN+10][30][30];
int C[MAXN+10][30][30];
void init(int _N, vector<int> _S, vector<int> _P, vector<int> _W, vector<int> _L)
{
N=_N;
for(int i=1; i<=N; i++)
{
S[i]=_S[i-1]; P[i]=_P[i-1];
W[i]=_W[i-1]+1; L[i]=_L[i-1]+1;
}
for(int i=0; i<=23; i++)
{
for(int j=1; j<=N; j++)
{
if(S[j]<(1<<i)) A[j][0][i]=S[j], B[j][0][i]=(1<<(i+1)), C[j][0][i]=W[j];
else if(S[j]<(1<<(i+1))) A[j][0][i]=P[j], B[j][0][i]=min((1<<(i+1)), S[j]), C[j][0][i]=L[j];
else A[j][0][i]=0, B[j][0][i]=0, C[j][0][i]=j;
}
A[N+1][0][i]=0, B[N+1][0][i]=0; C[N+1][0][i]=N+1;
for(int j=1; j<=25; j++)
{
for(int k=1; k<=N+1; k++)
{
C[k][j][i]=C[C[k][j-1][i]][j-1][i];
A[k][j][i]=A[k][j-1][i]+A[C[k][j-1][i]][j-1][i];
B[k][j][i]=min(B[k][j-1][i], B[C[k][j-1][i]][j-1][i]-A[C[k][j-1][i]][j-1][i]);
}
}
}
for(int i=1; i<=N; i++) A[i][0][24]=S[i], B[i][0][24]=INF, C[i][0][24]=W[i];
for(int j=1; j<=25; j++)
{
for(int k=1; k<=N+1; k++)
{
C[k][j][24]=C[C[k][j-1][24]][j-1][24];
A[k][j][24]=A[k][j-1][24]+A[C[k][j-1][24]][j-1][24];
B[k][j][24]=min(B[k][j-1][24], B[C[k][j-1][24]][j-1][24]-A[C[k][j-1][24]][j-1][24]);
}
}
}
ll simulate(int now, int x)
{
now++;
for(int i=0; i<=24; i++)
{
if(x>=(1<<(i+1))) continue;
for(int j=25; j>=0; j--)
{
if(x<B[now][j][i])
{
x+=A[now][j][i];
now=C[now][j][i];
}
}
if(now>N) break;
if(x<(1<<(i+1)))
{
if(x>=S[now]) x+=S[now], now=W[now];
else x+=P[now], now=L[now];
}
}
return x;
}
