#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const int I = 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 400 * 1000 + 7;
const int K = 16;
int pot3[K + 2];
int ts[N], tp[N], le[N], we[N];
int jp[K][K][N], req[K][K][N];
ll sum[K][K][N];
int n;
void DoP()
{
pot3[0] = 1;
for(int i = 1; i < K; ++i) pot3[i] = 3 * pot3[i - 1];
}
inline int P3(int x)
{
if(x == 0) return 0;
return (upper_bound(pot3, pot3 + K, x) - pot3) - 1;
}
void DoLCA(int n)
{
le[n + 1] = n + 1; we[n + 1] = n + 1;
for(int i = 0; i < K; ++i)
for(int j = 0; j < K; ++j)
{
sum[i][j][n + 1] = 0;
jp[i][j][n + 1] = n + 1;
req[i][j][n + 1] = -1;
}
for(int i = 1; i <= n; ++i)
{
int x = P3(ts[i]);
for(int j = 0; j < x; ++j)
{
req[j][0][i] = max(-1, 3 * pot3[j] - tp[i] - 1);
sum[j][0][i] = tp[i];
jp[j][0][i] = le[i];
}
req[x][0][i] = min(ts[i] - 1, 3 * pot3[x] - tp[i] - 1);
req[x][0][i] = max(req[x][0][i], -1);
sum[x][0][i] = tp[i];
jp[x][0][i] = le[i];
for(int j = x + 1; j < K; ++j)
{
req[j][0][i] = 3 * pot3[j] - 1 - ts[i];
sum[j][0][i] = ts[i];
jp[j][0][i] = we[i];
}
}
for(int j = 0; j < K; ++j)
for(int k = 1; k < K; ++k)
for(int i = 1; i <= n; ++i)
{
jp[j][k][i] = jp[j][k - 1][i];
sum[j][k][i] = sum[j][k - 1][i];
req[j][k][i] = req[j][k - 1][i];
for(int l = 1; l <= 2; ++l)
{
int ne = jp[j][k][i];
req[j][k][i] = max(-1LL, min((ll)req[j][k][i], (ll)req[j][k - 1][ne] - sum[j][k][i]));
sum[j][k][i] += sum[j][k - 1][ne];
jp[j][k][i] = jp[j][k - 1][ne];
}
}
}
ll Ans(int v, ll x, int n)
{
int j = 0;
while(v != n + 1)
{
while(j < K - 1 && pot3[j + 1] <= x) ++j;
for(int k = K - 1; k >= 0; --k)
for(int l = 1; l <= 2; ++l)
{
//if(k < 4)
//cout << j << " " << k << " " << v << " " << x << " : " << sum[j][k][v] << " " << req[j][k][v] << " " << jp[j][k][v] << "\n";
if(j == K - 1 || x <= req[j][k][v])
{
x += sum[j][k][v];
v = jp[j][k][v];
}
}
if(x >= (ll)ts[v])
{
x += (ll)ts[v];
v = we[v];
}else
{
x += (ll)tp[v];
v = le[v];
}
}
return x;
}
void init(int nx, vector<int> s, vector<int> p, vector<int> w, vector<int> l)
{
DoP(); n = nx;
for(int i = 1; i <= n; ++i)
{
ts[i] = s[i - 1]; tp[i] = p[i - 1];
we[i] = w[i - 1] + 1; le[i] = l[i - 1] + 1;
}
DoLCA(n);
return;
}
ll simulate(int x, int z)
{
int v = x + 1; x = z;
ll ans = Ans(v, x, n);
return ans;
}
