#ifdef LOCAL
#else
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#endif
#include <bits/stdc++.h>
#include "dungeons.h"
using namespace std;
#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
const ll inf = 1e9;
mt19937 rnd(234);
const ll bbr = 3;
const ll lgb = 16;
const ll lgn = 16;
const int mxn = 4e5;
int n;
bool s_eq_p;
bool few_dstnct;
vector<ll> s, p;
vector<int> w, l;
vector<array<ll, lgn>> bup, bup_mx, bup_sm;
int d;
vector<ll> dstnct;
vector<ll> layer;
struct dt {
int up;
int mn;
ll sm;
};
auto dbup = new dt[lgb][mxn + 1][lgn];
ll get_layer(ll x) {
ll cnt = 0;
while (x >= bbr) {
cnt += 1;
x /= bbr;
}
return min(cnt, lgb - 1);
}
void init_fuck() {
ll aboba = 1;
for (int lr = 0; lr < lgb; lr += 1) {
for (int i = 0; i <= n; i += 1) {
if (aboba >= s[i]) {
dbup[lr][i][0].up = w[i];
dbup[lr][i][0].sm = s[i];
dbup[lr][i][0].mn = inf;
} else {
dbup[lr][i][0].up = l[i];
dbup[lr][i][0].sm = p[i];
dbup[lr][i][0].mn = s[i];
}
}
for (int j = 1; j < lgn; j += 1) {
for (int i = 0; i <= n; i += 1) {
auto &[u, mn0, sm0] = dbup[lr][i][j - 1];
auto &[v, mn1, sm1] = dbup[lr][u][j - 1];
auto &[t, mn2, sm2] = dbup[lr][v][j - 1];
dbup[lr][i][j].up = t;
dbup[lr][i][j].sm = min((ll)(1e17), sm0 + sm1 + sm2);
dbup[lr][i][j].mn = max(-1ll, min((ll)mn0,
min((ll)mn1 - sm0, (ll)(mn2 - sm1 - sm0))));
}
}
aboba *= bbr;
}
}
void init(int _n, vector<int> _s, vector<int> _p, vector<int> _w, vector<int> _l) {
n = _n;
s.resize(n + 1);
p.resize(n + 1);
w.resize(n + 1);
l.resize(n + 1);
w[n] = l[n] = n;
s[n] = p[n] = 0;
for (int i = 0; i < n; i += 1) {
s[i] = _s[i];
p[i] = _p[i];
w[i] = _w[i];
l[i] = _l[i];
}
init_fuck();
return;
}
ll simulate_fuck(int x, ll z) {
for (int itr = 0; itr < 20 && x != n; itr += 1) {
if (s[x] <= z) {
z += s[x];
x = w[x];
// dz = s[x];
} else {
z += p[x];
x = l[x];
// dz = p[x];
}
}
while (x != n) {
int lr = get_layer(z);
if (dbup[lr][x][0].mn > min(z, inf / 2)) {
for (int j = lgn - 1; j >= 0; j -= 1) {
if (dbup[lr][x][j].mn > min(z, inf / 2)) {
z += dbup[lr][x][j].sm;
x = dbup[lr][x][j].up;
if (dbup[lr][x][j].mn > min(z, inf / 2)) {
z += dbup[lr][x][j].sm;
x = dbup[lr][x][j].up;
}
}
}
}
if (x == n) {
break;
}
// ll dz = -1;
z += s[x];
x = w[x];
if (x == n) {
break;
}
// assert(get_layer(dz) >= lr);
}
return z;
}
long long simulate(int x, int z) {
return simulate_fuck(x, z);
}
/*
3 1
2 6 9
3 1 2
2 2 3
1 0 1
2 3
*/