Background

Description

有一棵 $n$ 个节点的有根树，根节点为 1 。每个点的初始权值是 $a_i$ ，之后要进行 $m$ 轮操作。

1. 输入 $u,w$ ，给节点 $u$ 的权值加 $w$ ，给节点 $u$ 的所有子节点的权值减 $w$ ，给节点 $u$ 的所有子节点的子节点的权值加 $w$ ，以此类推。具体来说，如果说一个节点在 $u$ 的子树中，且到 $u$ 的距离为 $d$ ，则其权值会被加上 $(-1)^d w$ 。
2. 输入 $u$ ，输出节点 $u$ 的当前权值。

Format

Input

第一行两个整数 $n,m$ 。

第二行 $n$ 个整数 $a_1,a_2,\ldots ,a_n$ ($1\leq a_i\leq 10^3$) 。

接下来的 $n-1$ 行，每行两个整数 $x_i,y_i$ ($1\leq x_i,y_i\leq n$) ，表示树中一条节点 $x_i,y_i$ 之间的边。

接下来的 $m$ 行，每行一个操作，每行的第一个数表示进行的是哪种操作。

1. 1 u w 表示第一种操作 ($1\leq u\leq n,1\leq w\leq 1000$)
2. 2 u 表示第二种操作 ($1\leq u\leq n$)

Output

对于每个第二种操作，输出答案。

Samples

样例 1 输入

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

样例 1 输出

1
6
6

样例 1 解释

在第一次修改后，所有点的权值为 $[3,0,1,6,7]$ 。

在第二次修改后，所有点的权值为 $[3,0,2,5,6]$ 。

样例 2 输入

alter2.in

样例 2 输出

alter2.out

Limitation

对于 $30\%$ 的数据， $n,m\leq 5000$ 。

对于另外 $30\%$ 的数据，输入的树的结构是一条链。

对于 $100\%$ 的数据， $n,m\leq 2\times 10^5$ 。