#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];
        }
    }
    int lr = 0;
    ll lrbbr = 1;
    while (x != n) {
        while (lrbbr < z) {
            lrbbr *= bbr;
            lr += 1;
        }
        if (lr >= lgb) {
            z += dbup[lgb - 1][x][lgn - 1].sm;
            x = dbup[lgb - 1][x][lgn - 1].up;
        } else {
            if (dbup[lr][x][0].mn > min(z, inf / 2)) {
                for (int j = min((ll)lr, 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;
        }
        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

*/