题目描述
题目译自 JOISC 2022 Day3 T2「スプリンクラー / Sprinkler」。

JOI 君有多年在自家菜园种植蔬菜的经验，现在他计划管理 IOI 农场。

IOI 农场由 $N$ 块土地组成。土地间有 $N-1$ 条双向道路相连，编号从 $1$ 到 $N-1$，第 $i$ 条道路连接土地 $A_i$ 和 $B_i$，任意两块土地间都可以通过道路互达。农场的每块土地上都有一个洒水器，使用洒水器可以向附近的土地洒水。

JOI 君计划在 IOI 农场种植 JOI 谷。JOI 谷是一种奇特的作物，它在被浇水时高度会立刻发生变化。但是同时，JOI 谷是一种脆弱的植物，若它的高度大于等于 $L$，JOI 谷顶部长为 $L$ 的部分会立刻断裂并掉落。JOI 君会收获掉落的部分。

初始时，JOI 君在土地 $j$ 上种了一株高度为 $H_j$ 的 JOI 谷，之后的 $Q$ 天，JOI 君都会照料这些 JOI 谷，在第 $k$ 天，JOI 君会做如下两个操作之一：

• 操作 1：JOI 君使用土地 $X_k$ 上的洒水器，向与土地 $X_k$ 距离不超过 $D_k$ 的土地上浇水，使这些土地上的 JOI 谷高度乘以 $W_k$。由于 JOI 谷会不断断裂，因此若对一株原高度为 $h$ 的 JOI 谷洒水，它的高度会变为 $h \times W_k \bmod L$。
• 操作 2：JOI 君测量土地 $X_k$ 上 JOI 谷的高度。

土地 $x$ 和土地 $y$ 间距离的定义为：从土地 $x$ 前往土地 $y$ 经过道路数的最小值。

JOI 君希望 JOI 谷按照计划长大，因此，他希望提前算出每次操作 2 应当测量出 JOI 谷的高度。

---

输入格式
第一行两个整数 $N,L$，表示土地块数和 JOI 谷的断裂阈值。

接下来 $N-1$ 行，每行两个整数 $A_i,B_i$ 表示一条道路。

接下来 $N$ 行，每行一个整数 $H_i$ 表示 JOI 谷的初始高度。

接下来一行一个整数 $Q$ 表示操作次数。

接下来 $Q$ 行，第 $k$ 行以 $T_k$ 开头，表示这次操作类型，接下来：

• 若 $T_k=1$，这是一次操作 1，接下来三个整数 $X_k,D_k,W_k$ 分别表示洒水器编号，洒水半径和生长参数。
• 若 $T_k=2$，这是一次操作 2，接下来一个整数 $X_k$ 表示需要测量的 JOI 谷的编号。

---

输出格式
对于每一次操作 2，输出一个整数表示 JOI 谷的预期高度。

---

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

输出：

4
2
2
1
1
4
4
2

初始时，JOI 君在所有土地上种植了高度为 $1$ 的 JOI 谷。

第一天，JOI 君使用土地 $2$ 的洒水器，土地 $1,2,3$ 的 JOI 谷被影响，高度乘以 $2$，四株 JOI 谷的高度变为 $2,2,2,1$。

第二天，JOI 君使用土地 $1$ 的洒水器，土地 $1$ 的 JOI 谷被影响，高度乘以 $2$，四株 JOI 谷的高度变为 $4,2,2,1$。

第七天，JOI 君使用土地 $4$ 的洒水器，土地 $1,2,3,4$ 的 JOI 谷被影响，高度乘以 $2$，第一株 JOI 谷的高度变为 $8$，发生断裂，因此四株 JOI 谷的高度变为 $1,4,4,2$。

这组样例满足子任务 $1,5,6$ 的限制。

---

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

输出：

4
1
4
8
2

第一天，JOI 君使用土地 $5$ 的洒水器，土地 $5,6$ 上的 JOI 谷高度乘以 $7$，高度分别变为 $63,7$，因此，土地 $5$ 上的 JOI 谷会不断断裂，高度变为 $3$。

这组样例满足子任务 $1,2,3,6$ 的限制。

---

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

输出：

5
0
0
3
0
0
0

这组样例满足子任务 $1,3,4,6$ 的限制。

---

数据范围与提示
对于所有数据，满足：

• $2 \leq N \leq 200000$
• $2 \leq L \leq 10^9$
• $1 \leq A_i < B_i \leq N$ $(i \in [1,N-1])$
• 任意土地之间都可以通过若干条道路到达
• $0 \leq H_j < L$ $(1 \leq j \leq N)$
• $1 \leq Q \leq 400000$
• $T_k$ 均为 $1$ 或 $2$
• 对于满足 $T_k=1$ $(k \in [1, Q])$ 的 $k$，保证 $1 \leq X_k \leq N$, $0 \leq D_k \leq 40$, $0 \leq W_k < L$
• 对于满足 $T_k=2$ $(k \in [1, Q])$ 的 $k$，保证 $1 \leq X_k \leq N$

详细子任务附加限制及分值如下表所示：

子任务编号	附加限制	分值
1	$N,Q \le 1000$	3
2	对于满足 $T_k=1$ 的 $k$，保证 $D_k \leq 1$	9
3	对于满足 $T_k=1$ 的 $k$，保证 $D_k \leq 2$	29
4	对于满足 $T_k=1$ 的 $k$，保证 $W_k=0$	12
5	对于满足 $T_k=1$ 的 $k$，保证 $W_k=2$	30
6	无附加限制	17