题目描述

小 L 非常喜欢树。最近，他发现了一棵有趣的树。这棵树有 n 个节点( 1 到 n 编号)，节点 i 有一个初始的权值 $a_i$ 。这棵树的根是节点 1 。

这棵树有一个特殊的性质：当你给节点 i 的权值加 val 的时候，节点 i 的所有儿子的权值都会加 -val 。注意当你给节点i的儿子的权值加 -val 时，节点i的这个儿子的所有儿子的权值都会加 -(-val)，以此类推。样例说明可以很好地帮助你理解这个性质。

有 2 种操作：

操作(a). “1 x val” 表示给节点 x 的权值加 val 。

操作(b). “2 x” 输出节点 x 当前的权值。

为了帮助小 L 更好地理解这棵树，你必须处理 m 个操作。

输入格式

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

第二行包含 n 个整数 $a_1$，$a_2$，... ，$a_n$ ( 1 ≤ $a_i$ ≤ 1000 )。

接下来的 n-1 行，每行两个整数 u 和 v ( 1 ≤ u < v ≤ n )，表示节点 u 和节点 v 之间存在一条边。

接下来的 m 行，每行包含2种操作的一种。每个操作都保证 1 ≤ x ≤ n ，1 ≤ val ≤ 1000 。

数据规模

对于 50% 的数据，1 ≤ n ≤ 2000 ，1 ≤ m ≤ 2000 。

对于 100% 的数据，1 ≤ n ≤ 100000 ，1 ≤ m ≤ 100000 。

输出格式

对于每个操作(b) ，输出一个整数，表示节点 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] 。

第一个操作给节点 2 的权值增加 3 ，会给节点 2 的儿子 4、5 的权值增加 -3 。此时各个节点的权值变成 [1，5，1，-2，-1] 。

第二个操作给节点 1 的权值增加 2 ，会给节点 1 的儿子 2、3 的权值增加 -2 ，然后会给节点 2 的儿子 4、5 的权值增加 -(-2) 。各个节点的权值变成 [3，3，-1，0，1] 。