Large Wood Database (LWDB) 旨在安全地存储并对任意现有的树进行染色。LWDB 的更新提供了新的功能，因此是时候思考一下图论了。LWDB 中存储了一棵带权树。在 LWDB 管理系统（LWDB MS）的查询语言中，有两种类型的查询可用：

• 1 v d c — 将与节点 $v$ 距离不超过 $d$ 的所有树节点染成颜色 $c$。所有节点的初始颜色均为 $0$。
• 2 v — 返回节点 $v$ 的颜色。

你需要实现一个 LWDB MS 的原型，并响应所有用户的查询。

输入格式

第一行包含一个整数 $N$（$1 \le N \le 10^5$）— 树的节点数。

接下来的 $N-1$ 行包含树枝（边）的描述，每行包含三个数字 $a_i, b_i, w_i$（$1 \le a_i, b_i \le N, a_i \ne b_i, 1 \le w_i \le 10^4$），表示第 $i$ 条边连接节点 $a_i$ 和 $b_i$，且边权为 $w_i$。

下一行包含一个整数 $Q$（$1 \le Q \le 10^5$）— 查询的数量。

接下来的 $Q$ 行中，每行包含以下两种类型的查询之一：

• 数字 1 v d c（$1 \le v \le N, 0 \le d \le 10^9, 0 \le c \le 10^9$）。
• 数字 2 v（$1 \le v \le N$）。

输入中的所有数字均为整数。

输出格式

对于每个第二种类型的查询，在单独的一行中输出所查询节点的颜色。

样例

输入样例 1

5
1 2 30
1 3 50
3 4 70
3 5 60
8
1 3 72 6
2 5
1 4 60 5
2 3
2 2
1 2 144 7
2 4
2 5

输出样例 1

6
6
0
5
7