给定一棵有 $n$ 个节点的有根树，根节点为 $r = 1$，每个节点都有一个关联的权值 $a_i$。

树中两个节点之间的距离定义为它们之间最短路径上的边数。

节点 $x$ 的子树定义为所有满足“从 $y$ 到根节点 $r$ 的最短路径经过 $x$”的节点 $y$ 的集合。

你需要支持以下三种类型的操作：

1. 给定 $x, k, v$，对于每个与 $x$ 距离恰好为 $k$ 的节点 $y$，将 $a_y$ 更新为 $a_y + v$，然后输出 $a_y$ 的最大值。
2. 给定 $x, k, v$，对于每个与 $x$ 距离不超过 $k$ 的节点 $y$，将 $a_y$ 更新为 $a_y + v$，然后输出 $a_y$ 的最大值。
3. 给定 $x$ 和 $v$，对于节点 $x$ 子树中的每个节点 $y$，将 $a_y$ 更新为 $a_y + v$，然后输出 $a_y$ 的最大值。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试用例的数量。

对于每个测试用例，第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 2 \times 10^5$)，分别表示树的节点数和操作数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($-10^{14} \le a_i \le 10^{14}$)，表示每个节点的权值。

接下来的 $n-1$ 行，每行包含两个整数 $x$ 和 $y$ ($1 \le x, y \le n, x \neq y$)，表示树中的一条边。

接下来的 $q$ 行描述操作。每行包含三个或四个整数 $o, x, v$ 或 $o, x, k, v$ ($o \in \{1, 2, 3\}, 1 \le x \le n, 0 \le k < 10, -10^9 \le v \le 10^9$)，表示操作类型及其参数。

保证所有测试用例中 $n$ 的总和不超过 $5 \times 10^5$，所有测试用例中 $q$ 的总和不超过 $2 \times 10^5$。

输出格式

对于每个测试用例，输出 $q$ 行，每行包含一个整数，表示对应操作的结果。如果不存在有效的节点 $y$，则输出 GG。

样例

输入 1

1
5 5
1 2 1 3 2
1 2
2 3
2 4
4 5
2 2 1 0
1 2 1 3
3 4 -5
2 5 2 3
3 2 -1

输出 1

3
6
1
5
4

说明

初始节点权值为 $a = [1, 2, 1, 3, 2]$。

第 1 次操作后，权值保持为 $a = [1, 2, 1, 3, 2]$。

第 2 次操作后，权值变为 $a = [4, 2, 4, 6, 2]$。

第 3 次操作后，权值变为 $a = [4, 2, 4, 1, -3]$。

第 4 次操作后，权值变为 $a = [4, 5, 4, 4, 0]$。

第 5 次操作后，权值变为 $a = [4, 4, 3, 3, -1]$。