#include "dungeons.h"
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll;
namespace{
const ll mxN=4e5+5;
const ll LOG=21;
const ll inf=1e18;
ll n;
ll s[mxN], p[mxN], w[mxN], l[mxN];
array<ll, 3> up1[mxN][LOG]; // des, atleast, sum
array<ll, 3> up2[mxN][LOG];
array<ll, 3> mrg1(array<ll, 3> a, array<ll, 3> b){
array<ll, 3> re;
re[0]=b[0];
re[1]=max(a[1], b[1]-a[2]);
re[2]=a[2]+b[2];
return re;
}
array<ll, 3> mrg2(array<ll, 3> a, array<ll, 3> b){
array<ll, 3> re;
re[0]=b[0];
re[1]=min(a[1], b[1]-a[2]);
re[2]=a[2]+b[2];
return re;
}
}
void init(int N, vector<int> S, vector<int> P, vector<int> W, vector<int> L) {
n=N;
for(ll i=0;i<=n;i++){
s[i]=S[i];
p[i]=P[i];
w[i]=W[i];
l[i]=L[i];
}
for(ll i=0;i<n;i++){
up1[i][0]={w[i], s[i], s[i]};
up2[i][0]={l[i], s[i]-1, p[i]};
}
up1[n][0]={n, 0, 0};
up2[n][0]={n, inf, 0};
for(ll j=1;j<LOG;j++){
for(ll i=0;i<=n;i++){
up1[i][j]=mrg1(up1[i][j-1], up1[up1[i][j-1][0]][j-1]);
up2[i][j]=mrg2(up2[i][j-1], up2[up2[i][j-1][0]][j-1]);
}
}
}
long long simulate(int x, int z) {
ll ans=z;
while(x!=n){
if(ans>=s[x]){
for(ll i=LOG-1;i>=0;i--){
if(ans>=up1[x][i][1]){
ans+=up1[x][i][2];
x=up1[x][i][0];
}
}
}
else{
for(ll i=LOG-1;i>=0;i--){
if(ans<=up2[x][i][1]){
ans+=up2[x][i][2];
x=up2[x][i][0];
}
}
}
}
return ans;
}
