题目描述

JOI 国由 $N$ 座城市和 $N-1$ 条高速公路组成。这些城市的编号为 $1$ 到 $N$，高速公路的编号为 $1$ 到 $N-1$。通过穿过若干条高速公路，可以从任何一座城市到达任何其他城市。

每座城市都有一个热度，用一个非负整数表示。城市 $i$（$1 \leq i \leq N$）的初始热度为 $C_i$。每条高速公路都有一个通行时间，用一个正整数表示。高速公路 $j$（$1 \leq j \leq N-1$）连接着城市 $A_j$ 和城市 $B_j$，其初始通行时间为 $D_j$。

JOI 国的每座城市都有一个圣火盆。JOI 国保持着一个传统，即在节日里，各个城市会点燃它们的圣火盆，这些点火仪式标志着游行队伍从这些城市出发。

如果两座城市由一条高速公路直接相连，则城市 $u$ 与城市 $v$ 是相邻的。在某座城市点燃其圣火盆的准确瞬间，将有一支游行队伍从该城市出发前往其每个相邻的城市，所花费的时间等于对应高速公路的通行时间。准确地说，对于两个相邻的城市 $v$ 和 $u$，从城市 $v$ 出发的游行队伍在时间 $t + d$ 到达城市 $u$，其中 $t$ 是城市 $v$ 的圣火盆被点燃的时间，$d$ 是连接城市 $v$ 和 $u$ 的高速公路的通行时间。

有些城市在节日开始的瞬间就会点燃它们的圣火盆，而另一些城市则只有在节日气氛足够热烈后才会这样做。令时间 $0$ 为节日的开始。对于热度为 $c$ 的城市 $i$，城市 $i$ 点燃其圣火盆的时间按如下方式确定：

• 如果 $c = 0$，城市 $i$ 在时间 $0$ 点燃其圣火盆。
• 如果 $c \geq 1$，当从相邻城市到达的游行队伍数量至少达到 $c$ 时，城市 $i$ 就会点燃其圣火盆。如果这种情况永远没有发生，城市 $i$ 就永远不会点燃其圣火盆。

K 先生将在 JOI 国逗留。在他逗留期间，JOI 国将发生 $Q$ 个与其节日相关的事件。这些事件按照发生时间从早到晚编号为 $1$ 到 $Q$。

事件 $k$（$1 \leq k \leq Q$）是以下 $3$ 种类型之一：

• 类型 $1$：城市 $V_k$ 的热度变为 $X_k$。
• 类型 $2$：高速公路 $E_k$ 的通行时间变为 $X_k$。
• 类型 $3$：K 先生访问城市 $V_k$。假设一个节日在此刻开始，你必须确定城市 $V_k$ 是否会点燃其圣火盆，如果会，计算出圣火盆被点燃的时间。

编写一个程序，在给定 JOI 国的结构、每座城市的热度、每条高速公路的通行时间以及事件详情的情况下，对于每个类型 $3$ 的事件，确定 K 先生访问的城市何时点燃其圣火盆。

输入格式

从标准输入读取以下数据。

$N$
$A_1\ B_1\ D_1$
$\vdots$
$A_{N-1}\ B_{N-1}\ D_{N-1}$
$C_1$
$\vdots$
$C_N$
$Q$
(Query $1$)
$\vdots$
(Query $Q$)

(Query $k$) 表示事件 $k$（$1 \leq k \leq Q$）的详情。在 (Query $k$) 中，写入了以空格分隔的整数。令 $P_k$ 为第一个整数。$P_k$ 为 $1$、$2$ 或 $3$，表示事件 $k$ 的类型。那么 (Query $k$) 的含义如下：

• 如果 $P_k = 1$，则后面还按此顺序写入了两个整数 $V_k, X_k$。这意味着城市 $V_k$ 的热度变为了 $X_k$。
• 如果 $P_k = 2$，则后面还按此顺序写入了两个整数 $E_k, X_k$。这意味着高速公路 $E_k$ 的通行时间变为了 $X_k$。
• 如果 $P_k = 3$，则后面还写入了一个整数 $V_k$。这意味着 K 先生访问了城市 $V_k$，并且假设一个节日在此刻开始，你必须确定城市 $V_k$ 的圣火盆被点燃的时间。

输出格式

向标准输出输出，对于每个 $P_k = 3$ 的事件 $k$（$1 \le k \le Q$），按照 $k$ 递增的顺序，每行输出以下内容：

• 如果 K 先生访问的城市会点燃其圣火盆，输出该圣火盆被点燃的时间。
• 否则，输出 $\texttt{-1}$。

7
1 2 30
2 3 30
1 4 70
2 5 20
1 6 10
2 7 50
2
3
0
0
0
1
0
8
3 1
1 6 0
3 1
2 6 10
3 1
1 2 7
1 6 7
3 1

80
70
60
-1

6
1 2 10
1 3 30
1 4 50
1 5 30
1 6 10
2
0
0
0
0
1
10
3 1
2 3 20
3 1
1 6 0
3 1
1 1 4
3 1
1 2 6
1 3 6
3 1

30
20
10
30
-1

提示

样例 1

在事件 $1$ 考虑的节日中，各城市点燃圣火盆的时间如下：

• 在时间 $0$，城市 $3, 4, 5, 7$ 点燃了它们的圣火盆。
• 在时间 $50$，城市 $2$ 点燃了它的圣火盆。到那时，来自城市 $3, 5, 7$ 的游行队伍已经到达了城市 $2$。
• 在时间 $80$，城市 $1$ 点燃了它的圣火盆。到那时，来自城市 $2, 4$ 的游行队伍已经到达了城市 $1$。
• 在时间 $90$，城市 $6$ 点燃了它的圣火盆。到那时，来自城市 $1$ 的游行队伍已经到达了城市 $6$。 由于城市 $1$ 会在时间 $80$ 点燃其圣火盆，因此输出 $80$。

在事件 $3$ 考虑的节日中，各城市点燃圣火盆的时间如下：

• 在时间 $0$，城市 $3, 4, 5, 6, 7$ 点燃了它们的圣火盆。
• 在时间 $50$，城市 $2$ 点燃了它的圣火盆。到那时，来自城市 $3, 5, 7$ 的游行队伍已经到达了城市 $2$。
• 在时间 $70$，城市 $1$ 点燃了它的圣火盆。到那时，来自城市 $4, 6$ 的游行队伍已经到达了城市 $1$。 由于城市 $1$ 会在时间 $70$ 点燃其圣火盆，因此输出 $70$。

在事件 $5$ 考虑的节日中，各城市点燃圣火盆的时间如下：

• 在时间 $0$，城市 $3, 4, 5, 6, 7$ 点燃了它们的圣火盆。
• 在时间 $30$，城市 $2$ 点燃了它的圣火盆。到那时，来自城市 $3, 5, 7$ 的游行队伍已经到达了城市 $2$。
• 在时间 $60$，城市 $1$ 点燃了它的圣火盆。到那时，来自城市 $2, 6$ 的游行队伍已经到达了城市 $1$。 由于城市 $1$ 会在时间 $60$ 点燃其圣火盆，因此输出 $60$。

在事件 $8$ 考虑的节日中，各城市点燃圣火盆的时间如下：

• 在时间 $0$，城市 $3, 4, 5, 7$ 点燃了它们的圣火盆。 城市 $1, 2, 6$ 永远不会点燃它们的圣火盆。由于城市 $1$ 永远不会点燃其圣火盆，因此输出 $-1$。 此样例输入满足子任务 $1, 3, 5, 7$ 的约束条件。

样例 2

此样例输入满足子任务 $1, 2, 5, 7$ 的约束条件。

约束条件

• $2 \le N \le 150000$。
• $0 \le C_i \le N$ ($1 \le i \le N$)。
• $1 \le A_j < B_j \le N$ ($1 \le j \le N-1$)。
• $1 \le D_j \le 1000000$ ($1 \le j \le N-1$)。
• 通过穿过若干条高速公路，可以从任何一座城市到达任何其他城市。
• $1 \le Q \le 150000$。
• 如果 $P_k = 1$，则有 $1 \le V_k \le N$, $0 \le X_k \le N$ ($1 \le k \le Q$)。
• 如果 $P_k = 2$，则有 $1 \le E_k \le N-1$, $1 \le X_k \le 1000000$ ($1 \le k \le Q$)。
• 如果 $P_k = 3$，则有 $1 \le V_k \le N$ ($1 \le k \le Q$)。
• 给定的值均为整数。

子任务

1. (6 分) $N \le 2000$, $Q \le 2000$。
2. (7 分) $A_j = 1$, $B_j = j+1$ ($1 \le j \le N-1$)。如果 $P_k = 3$，则有 $V_k = 1$ ($1 \le k \le Q$)。
3. (14 分) $N-1$ 能被 $3$ 整除。$A_j = ((j-1) \mod \frac{N-1}{3}) + 1$, $B_j = j+1$ ($1 \le j \le N-1$)。如果 $P_k = 3$，则有 $V_k = 1$ ($1 \le k \le Q$)。
4. (25 分) $P_k \ne 1$。如果 $P_k = 3$，则有 $V_k = 1$ ($1 \le k \le Q$)。
5. (12 分) 如果 $P_k = 3$，则有 $V_k = 1$ ($1 \le k \le Q$)。
6. (22 分) $P_k \ne 1$ ($1 \le k \le Q$)。
7. (14 分) 无附加约束条件。