给出一棵包含 $n$ 个点的树，每个节点 $i$ 都有一个权值 $a_i$。

有 $m$ 次操作，每次操作都形如以下的两种：

• 1 x y：查询 $x$ 到 $y$ 的路径上，最大的点权权值。
• 2 x z：对于所有与 $x$ 直接相连的点 $i$，令 $a_i \leftarrow a_i+z$。

不保证查询的 $x,y$ 满足 $x \ne y$。

输入格式

每个测试点中包含多组测试数据。输入的第一行包含一个正整数 $T$ $(1 \le T \le 110)$，表示数据组数。

对于每组测试数据：

• 第一行两个正整数 $n,m$ $(1 \le n,m \le 10^5)$。
• 第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$ $(1 \le a_i \le 10^4)$，表示初始每个节点的点权。
• 接下来 $n-1$ 行，每行两个正整数 $x,y$ $(1 \le x,y \le n)$，表示有一条从 $x$ 到 $y$ 的无向边。
• 接下来 $m$ 行，每行三个整数，第一个数 $opt$ 表示操作类型：
  • 若 $opt=1$，则后面两个数 $x,y$ $(1 \le x,y \le n)$，表示询问路径。
  • 若 $opt=2$，则后面两个数 $x,z$ $(1 \le x \le n,1 \le z \le 10^4)$，分别表示修改中心以及增加的值。

保证所有测试数据中 $n$ 之和与 $m$ 之和均不超过 $4 \times 10^5$。

输出格式

对于每组测试数据：对于每一个 $opt=1$ 的操作，输出一行一个数表示答案。

样例

输入

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

输出

9
11
17
13