JOI 王国由 $N$ 个城市和 $N-1$ 条公路组成。城市编号为 $1$ 到 $N$，公路编号为 $1$ 到 $N-1$。通过若干条公路，可以从任意城市到达其他任意城市。

每个城市都有一个非负整数表示的人气值。城市 $i$ ($1 \le i \le N$) 的初始人气值为 $C_i$。每条公路都有一个正整数表示的通行时间。公路 $j$ ($1 \le j \le N-1$) 连接城市 $A_j$ 和城市 $B_j$，其初始通行时间为 $D_j$。

JOI 王国的每个城市都有一个大锅。王国保留着一项传统：在节日期间，城市会点燃它们的大锅，这些点火信号标志着从这些城市出发的游行队伍的启程。

如果两个城市之间直接由一条公路相连，则称城市 $u$ 与城市 $v$ 相邻。在城市点燃大锅的瞬间，该城市会向其每个相邻城市各派出一支游行队伍，耗时等于相应公路的通行时间。具体来说，对于两个相邻城市 $v$ 和 $u$，从城市 $v$ 出发的游行队伍在时间 $t+d$ 到达城市 $u$，其中 $t$ 是城市 $v$ 点燃大锅的时间，$d$ 是连接城市 $v$ 和 $u$ 的公路的通行时间。

有些城市在节日开始时立即点燃大锅，而其他城市则在节日气氛足够热烈后才点燃。设时间 $0$ 为节日开始的时间。对于人气值为 $c$ 的城市 $i$，其点燃大锅的时间确定如下：

• 如果 $c = 0$，城市 $i$ 在时间 $0$ 点燃大锅。
• 如果 $c \ge 1$，城市 $i$ 在从相邻城市到达的游行队伍数量达到至少 $c$ 的时刻点燃大锅。如果这种情况从未发生，则城市 $i$ 永远不会点燃大锅。

K 先生将留在 JOI 王国。在他逗留期间，JOI 王国将举办 $Q$ 个与节日相关的事件。这些事件按时间先后顺序编号为 $1$ 到 $Q$。

事件 $k$ ($1 \le k \le 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 \le k \le 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 先生访问的城市会点燃大锅，输出点燃大锅的时间。
• 否则，输出 -1。

数据范围

• $2 \le N \le 150\,000$。
• $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 1\,000\,000$ ($1 \le j \le N-1$)。
• 可以通过若干条公路从任意城市到达其他任意城市。
• $1 \le Q \le 150\,000$。
• 如果 $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 1\,000\,000$ ($1 \le k \le Q$)。
• 如果 $P_k = 3$，则 $1 \le V_k \le N$ ($1 \le k \le Q$)。
• 给定值均为整数。

子任务

1. (6 分) $N \le 2\,000, Q \le 2\,000$。
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) \pmod{\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 \neq 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 \neq 1$ ($1 \le k \le Q$)。
7. (14 分) 无附加限制。

样例

样例输入 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

样例输出 1

80
70
60
-1

样例输入 2

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

样例输出 2

30
20
10
30
-1