#include "dungeons.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "Ofast")
#define ll long long
#define se second
#define fi first
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
typedef pair<ll,ll> pii;
typedef pair<pii,pii> ipii;
const int MAXN = 4e5+10;
const int MAXA = 5e4+10;
const int SQRT = 300;
const ll INF = 1e9;
const int MOD = 998244353;
const int LOG = 40;
ll n, s[MAXN], p[MAXN], w[MAXN], l[MAXN];
vector<array<ll,3>> vec[MAXN];
ll up[MAXN];
void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::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=n; i>=1; i--){
// dia tuh win, at least s[i]
ll base = s[i], id = w[i];
bool done = 0;
for(auto [mn, idx, wei] : vec[w[i]]){
// mn-s[i]
if(mn-s[i] <= s[i]){
if(base < wei+s[i]){
base = wei+s[i]; id = idx;
}
} else {
if(!done){
done = 1;
vec[i].pb({s[i], id, base});
}
vec[i].pb({mn-s[i], idx, wei+s[i]});
}
}
if(!done) vec[i].pb({s[i], id, base}); // kalo lebih dr p, ke idx, +wei
if(vec[i].size() > 15) assert(false);
// cout << i << " i\n";
// for(auto [a,b,c] : vec[i]) cout << a<<' '<<b<<' '<<c<<" pp\n";
}
return;
}
long long simulate(int x, int z) {
ll idx = x+1, pow = z;
while(idx != n+1){
if(s[idx] > pow){ // lose
pow += p[idx];
idx = l[idx];
continue;
}
array<ll,3> te = {pow, INF, INF};
int id = lower_bound(vec[idx].begin(), vec[idx].end(), te)-vec[idx].begin()-1;
auto ret = vec[idx][id];
pow += ret[2];
idx = ret[1];
}
return pow;
}
