题目描述

$\text{Iahub}$ 喜欢树。最近他发现了一种有趣的树，名为传播树。这棵树由编号从 $1$ 到 $n$ 的 $n$ 个节点组成，每个节点 $i$ 具有初始值 $a_i$。树的根节点是节点 $1$。

这棵树有一个特殊的属性：当将值 $val$ 添加到节点 $i$ 的值时，值 $-val$ 将添加到节点 $i$ 的所有子节点的值中。请注意，当你向节点 $i$ 的子节点添加值 $-val$ 时，你也会向节点 $i$ 的所有子节点的所有子节点中添加 $-(-val)$ ，以此类推。

这棵树支持两种类型的操作：

• $1$ $x$ $val$ — 将 $val$ 添加到节点 $x$ 的值；
• $2$ $x$ — 输出节点 $x$ 的当前值。

为了帮助 $\text{Iahub}$ 更好地理解这棵树，你必须回答前述类型的 $m$ 个查询。

输入格式

第一行包含两个整数 $n$ 和 $m$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

接下来的 $n-1$ 行中，每行包含两个整数 $v_i$ 和 $u_i$ ($1 \le v_i,u_i \le n$)，表示节点 $v_i$ 和节点 $u_i$ 之间有一条边。

接下来的 $m$ 行中，每行包含一个按上述格式描述的查询。

保证对于所有查询，以下约束条件成立：$1 \le x \le n,1 \le val \le 1000$。

输出格式

对于每个类型为 $2$ 的查询（输出节点 $x$ 的值），你必须将查询的答案单独输出在一行上。必须按照输入中给定的顺序回答查询。

5 5
1 2 1 1 2
1 2
1 3
2 4
2 5
1 2 3
1 1 2
2 1
2 2
2 4

3
3
0

样例分析

节点的值在开始时为 $[1,2,1,1,2]$。

然后将值 $3$ 添加到节点 $2$。它传播，值 $-3$ 被添加到它的子节点，节点 $4$ 和节点 $5$ 。然后它无法再传播。因此，节点的值为 $[1,5,1,-2,-1]$。

然后将值 $2$ 添加到节点 $1$ 。它传播，值 $-2$ 被添加到它的子节点，节点 $2$ 和节点 $3$ 。从节点 $2$ 再次传播，将值 $2$ 添加到它的子节点，节点 $4$ 和节点 $5$。节点 $3$ 没有子节点，所以它无法从那里传播。节点的值为 $[3,3,-1,0,1]$。

数据范围与提示

对于 $100\%$ 的数据：$1 \le n,m \le 2 \times 10^5$，$1 \le a_i \le 1000$。