小 L 非常喜欢树。最近，他发现了一棵有趣的树。这棵树有 n 个节点(1 到 n 编号)，节点 i 有一个 初始的权值 ai。这棵树的根是节点 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。

对于每个操作(b)，输出一个整数，表示节点 x 当前的权值。

【输入输出样例解释】

初始各个节点的权值依次为[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]。

【数据说明】

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