JOI-kun 在他的家庭菜园里种植蔬菜已有多年经验。现在，他计划管理 IOI 农场。

IOI 农场由 $N$ 块土地组成，编号为 $1$ 到 $N$。有 $N-1$ 条道路连接这些土地，编号为 $1$ 到 $N-1$。第 $i$ 条道路（$1 \le i \le N-1$）双向连接土地 $A_i$ 和土地 $B_i$。通过这些道路，可以从任意一块土地移动到其他任何一块土地。每块 IOI 农场的土地上都有一个喷水器。使用喷水器，我们可以向周围的土地喷水。

JOI-kun 计划在 IOI 农场种植 JOI 粟。JOI 粟是一种奇特的植物。如果我们浇水，JOI 粟的高度会立即改变。但是，JOI 粟是一种脆弱的植物。如果 JOI 粟的高度变得大于或等于 $L$，其长度为 $L$ 的顶部会立即折断。JOI-kun 将收获折断的 JOI 粟部分。

起初，JOI-kun 在土地 $j$（$1 \le j \le N$）上种植了一株高度为 $H_j$ 的 JOI 粟。此后，在 $Q$ 天内，JOI-kun 每天都会照料这些 JOI 粟。在第 $k$ 天（$1 \le k \le Q$），JOI-kun 会执行以下操作之一：

• 类型 1：JOI-kun 使用土地 $X_k$ 的喷水器，向所有与土地 $X_k$ 的距离小于或等于 $D_k$ 的土地喷水。如果某块土地被喷水，该土地上的 JOI 粟就会生长，其高度乘以 $W_k$。但是，当高度变得大于或等于 $L$ 时，JOI 粟长度为 $L$ 的顶部会立即折断。因此，如果 JOI-kun 给一株高度为 $h$ 的 JOI 粟浇水，该 JOI 粟的高度最终会变为 “$h \times W_k$ 除以 $L$ 的余数”。
• 类型 2：JOI-kun 测量土地 $X_k$ 上 JOI 粟的高度。

这里，从土地 $x$（$1 \le x \le N$）到土地 $y$（$1 \le y \le N$）的距离是指从土地 $x$ 移动到土地 $y$ 所必须经过的最少道路数量。

JOI-kun 希望看到 JOI 粟按计划生长。为此，他想提前计算出每次类型 2 操作所测得的 JOI 粟高度。

编写一个程序，在给定 IOI 农场信息和 JOI-kun 的计划后，计算出 JOI-kun 每次执行类型 2 操作时所测得的 JOI 粟高度。

输入格式

从标准输入读取以下数据。所有给定的值均为整数。

$N \ L$ $A_1 \ B_1$ $A_2 \ B_2$ $\vdots$ $A_{N-1} \ B_{N-1}$ $H_1$ $H_2$ $\vdots$ $H_N$ $Q$ (查询 1) (查询 2) $\vdots$ (查询 $Q$)

每个 (查询 $k$)（$1 \le k \le Q$）由空格分隔的整数组成。设 $T_k$ 为 (查询 $k$) 的第一个整数。该行的内容为以下之一：

• 如果 $T_k = 1$，该行还包含三个空格分隔的整数 $X_k, D_k, W_k$。这意味着 JOI-kun 在第 $k$ 天执行类型 1 操作，JOI-kun 向所有与土地 $X_k$ 的距离小于或等于 $D_k$ 的土地喷水，且浇水后 JOI 粟的高度乘以 $W_k$。
• 如果 $T_k = 2$，该行还包含一个整数 $X_k$。这意味着 JOI-kun 在第 $k$ 天执行类型 2 操作，JOI-kun 测量土地 $X_k$ 上 JOI 粟的高度。

输出格式

对于每次类型 2 的操作（即对于每个 $T_k = 2$ 的 $k$（$1 \le k \le Q$）），按顺序将第 $k$ 天类型 2 操作测得的土地 $X_k$ 上的 JOI 粟高度输出到标准输出。输出应以换行符分隔。

数据范围

• $2 \le N \le 200\,000$
• $2 \le L \le 1\,000\,000\,000 \ (= 10^9)$
• $1 \le A_i < B_i \le N \ (1 \le i \le N-1)$
• 可以通过道路从任意土地移动到其他任何土地。
• $0 \le H_j \le L-1 \ (1 \le j \le N)$
• $1 \le Q \le 400\,000$
• $T_k$ 为 $1$ 或 $2 \ (1 \le k \le Q)$
• 对于每个 $T_k = 1$ 的 $k \ (1 \le k \le Q)$，满足以下不等式： $1 \le X_k \le N, \ 0 \le D_k \le 40, \ 0 \le W_k \le L-1$
• 对于每个 $T_k = 2$ 的 $k \ (1 \le k \le Q)$，满足不等式 $1 \le X_k \le N$

子任务

1. (3 分) $N \le 1\,000, \ Q \le 1\,000$
2. (9 分) 对于每个 $T_k = 1$ 的 $k \ (1 \le k \le Q)$，满足 $D_k \le 1$
3. (29 分) 对于每个 $T_k = 1$ 的 $k \ (1 \le k \le Q)$，满足 $D_k \le 2$
4. (12 分) 对于每个 $T_k = 1$ 的 $k \ (1 \le k \le Q)$，满足 $W_k = 0$
5. (30 分) 对于每个 $T_k = 1$ 的 $k \ (1 \le k \le Q)$，满足 $W_k = 2$
6. (17 分) 无附加限制

样例

样例输入 1

4 7
1 2
2 3
3 4
1
1
1
1
11
1 2 1 2
1 1 0 2
2 1
2 2
2 3
2 4
1 4 10 2
2 1
2 2
2 3
2 4

样例输出 1

4
2
2
1
1
4
4
2

样例输入 2

6 10
5 6
1 2
1 4
2 6
3 6
9
2
3
4
9
1
10
1 5 1 7
2 4
1 4 1 9
1 5 0 7
2 1
1 1 1 3
1 6 1 4
2 5
2 4
2 3

样例输出 2

4
1
4
8
2

样例输入 3

8 10
1 3
3 5
4 7
6 7
4 5
7 8
2 4
5
8
6
4
6
2
9
3
11
1 2 2 0
2 1
1 6 1 0
2 4
2 6
1 5 2 0
2 8
1 7 2 0
2 6
2 7
2 4

样例输出 3

5
0
0
3
0
0
0