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

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

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

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

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

第一行两个正整数 $n, m(1 \leq n, m \leq 10^5)$。

第二行 $n$ 个整数 $a_1, a_2, \cdots, a_n(1 \leq a_i \leq 10^4)$，表示初始每个节点的点权。

接下来 $n - 1$ 行，每行两个正整数 $x, y(1 \leq x, y \leq n)$，表示有一条从 $x$ 到 $y$ 的无向边。

接下来 $m$ 行，每行三个整数，第一个数 $\mathrm{opt}$ 表示操作类型：

• 若 $\mathrm{opt} = 1$，则后面两个数 $x, y(1 \leq x, y \leq n)$，表示询问路径。
• 若 $\mathrm{opt} = 2$，则后面两个数 $x, z(1 \leq x \leq n, 1 \leq z \leq 10^4)$，分别表示修改中心以及增加的值。

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

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