题目描述

很久以前，有一棵神橡树(oak)，上面有$n$个节点，从$1$~$n$编号，由$n-1$条边相连。它的根是$1$号节点。

这棵橡树每个点都有一个权值，你需要完成这两种操作： $1$ $u$ $val$ 表示给$u$节点的权值增加$val$
$2$ $u$ 表示查询$u$节点的权值

但是这不是普通的橡树，它是神橡树。
所以它还有个神奇的性质：当某个节点的权值增加$val$时，它的子节点权值都增加$-val$，它子节点的子节点权值增加$-(-val)$...... 如此一直进行到树的底部。

输入输出格式

输入格式：

第一行两个正整数$n,m$，表示节点数量和操作数量。
第二行$n$个正整数$a_i$，依次表示每个节点的权值。
接下来$n-1$行，每行两个正整数$u,v$，表示$u,v$之间有一条边相连。
最后$m$行，每行若干个正整数，表示一次操作。

输出格式：

对于每次询问，输出一行一个整数表示答案。

说明

数据范围：

$1\le n,m \le 2\times 10^5$
$1\le a_i,val \le 1000$
$1\le u,v \le n$

样例 #1

样例输入 #1

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

样例输出 #1

3
3
0