题目描述

Iahub 非常喜欢树。最近他发现了一种有趣的树，叫作传播树。这棵树由 $n$ 个节点组成，节点编号从 $1$ 到 $n$，每个节点 $i$ 都有一个初始值 $a_{i}$。这棵树的根是节点 $1$。

这棵树有一个特殊性质：当一个值 $val$ 被加到节点 $i$ 的值上时，值 $-val$ 会被加到节点 $i$ 的所有子节点的值上。注意，当你把值 $-val$ 加到节点 $i$ 的某个子节点上时，你也会把 $-(-val)$ 加到该子节点的所有子节点上，依此类推。请查看样例说明，以便更好地理解它的工作方式。

这棵树支持两种类型的询问：

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

为了帮助 Iahub 更好地理解这棵树，你必须回答 $m$ 个上述类型的询问。

输入格式

第一行包含两个整数 $n$ 和 $m$ $(1 \le n,m \le 200000)$。第二行包含 $n$ 个整数 $a_{1}$，$a_{2}$，...，$a_{n}$ $(1 \le a_{i} \le 1000)$。接下来的 $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$。

输出格式

对于每个类型二的询问（输出节点 $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]$。

你可以在以下链接查看关于树的所有定义： http://en.wikipedia.org/wiki/Tree\_(graph\_theory)