#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) {
    while (x != n) {
        int lr = get_layer(z);
        if (dbup[lr][x][0].mn <= z) {
            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;
                    }
                }
            }
        }
        // ll dz = -1;
        if (s[x] <= z) {
            z += s[x];
            x = w[x];
            // dz = s[x];
        } else {
            z += p[x];
            x = l[x];
            // dz = p[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

*/

In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from answer.code:8:
/usr/include/c++/13/bits/allocator.h: In destructor ‘std::_Vector_base<long long int, std::allocator<long long int> >::_Vector_impl::~_Vector_impl()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = long long int]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/vector:66,
                 from /usr/include/c++/13/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53:
/usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here
  133 |       struct _Vector_impl
      |              ^~~~~~~~~~~~