You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

【某张 CG】

为什么。。。明明是我先来的。

什么破游戏。小巡关掉了游戏开始做一个简单的数据结构题。

有一颗 $n$ 个节点的树（以 $1$ 为根），每个点有点权 $a_i$。维护三种操作：

• 1 x k v 把所有和 $x$ 距离恰好 $k$ 的点点权自增 $v$。然后输出这些点点权的最大值。
• 2 x k v 把所有和 $x$ 距离不超过 $k$ 的点点权自增 $v$。然后输出这些点点权的最大值。
• 3 x v 把所有和 $x$ 子树内的点点权自增 $v$。然后输出这些点点权的最大值。

如果这样的点不存在，输出 nie。

Input

本题多测。

第一行一个正整数 $T$ 表示测试点数量。

每个测试点，第一行两个正整数表示 $n,m$。

接下来一行，$n$ 个正整数表示 $a_i$。

接下来 $n-1$ 行，每行两个正整数描述了一条树边。

接下来 $m$ 行，每行描述一个操作。

Output

对每个操作，输出答案。

Examples

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

Constraints

对所有数据，满足 $1\leq n\leq 10^5$，$1\leq m\leq 5\times 10^4$，$1\leq T\leq 5$，$1\leq k\leq 10$。输入的数不会超过 $10^9$。