Iahub likes trees very much. Recently he discovered an interesting tree named propagating tree. The tree consists of *n* nodes numbered from 1 to *n*, each node *i* having an initial value *a*<sub class="lower-index">*i*</sub>. The root of the tree is node 1.

This tree has a special property: when a value *val* is added to a value of node *i*, the value -*val* is added to values of all the children of node *i*. Note that when you add value -*val* to a child of node *i*, you also add -(-*val*) to all children of the child of node *i* and so on. Look an example explanation to understand better how it works.

This tree supports two types of queries:
 -  "1 *x* *val*" — *val* is added to the value of node *x*; -  "2 *x*" — print the current value of node *x*. 
In order to help Iahub understand the tree better, you must answer *m* queries of the preceding type.
The first line contains two integers *n* and *m* (1 ≤ *n*, *m* ≤ 200000). The second line contains *n* integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 1000). Each of the next *n*–1 lines contains two integers *v*<sub class="lower-index">*i*</sub> and *u*<sub class="lower-index">*i*</sub> (1 ≤ *v*<sub class="lower-index">*i*</sub>, *u*<sub class="lower-index">*i*</sub> ≤ *n*), meaning that there is an edge between nodes *v*<sub class="lower-index">*i*</sub> and *u*<sub class="lower-index">*i*</sub>.

Each of the next *m* lines contains a query in the format described above. It is guaranteed that the following constraints hold for all queries: 1 ≤ *x* ≤ *n*, 1 ≤ *val* ≤ 1000.
#include<bits/stdc++.h>
using namespace std;
int const N=233333;
int n,q,cur,a[N],l[N],r[N],d[N];
vector<int>e[N];
struct fenwick_tree{
int tr[N];
void clr(){
memset(tr,0,sizeof tr);
}
void add(int x,int y){
for(;x<N;x+=x&-x)tr[x]+=y;
}
int ask(int x){
return x?ask(x&(x-1))+tr[x]:0;
}
void add(int l,int r,int k){
add(l,k),add(r+1,-k);
}
};
fenwick_tree tr[2];
void dfs(int x,int fa){
l[x]=++cur,d[x]=!d[fa];
reverse(e[x].begin(),e[x].end());
for(int y:e[x])if(y^fa)dfs(y,x);
r[x]=cur;
}
int main(){
ios::sync_with_stdio(0);
cin>>n>>q;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1,x,y;i<n;i++)
cin>>x>>y,e[x].push_back(y),e[y].push_back(x);
dfs(1,0);
for(int op,x,y;q--;){
if(cin>>op>>x,op<2)
cin>>y,tr[d[x]].add(l[x],r[x],y),tr[!d[x]].add(l[x],r[x],-y);
else cout<<a[x]+tr[d[x]].ask(l[x])<<"\n";
}
}