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*_{*i*}$. 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.

Input

The first line contains two integers $*n*$ and $*m*$ $(1 ≤ *n*, *m* ≤ 200000)$. The second line contains $*n*$ integers $*a*_{1}$, $*a*_{2}$, ..., $*a*_{*n*}$ $(1 ≤ *a*_{*i*} ≤ 1000)$. Each of the next $*n*–1$ lines contains two integers $*v*_{*i*}$ and $*u*_{*i*}$ $(1 ≤ *v*_{*i*}, *u*_{*i*} ≤ *n*)$, meaning that there is an edge between nodes $*v*_{*i*}$ and $*u*_{*i*}$.

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$.

Output

For each query of type two (print the value of node $*x*$) you must print the answer to the query on a separate line. The queries must be answered in the order given in the input.

Note

The values of the nodes are $[1, 2, 1, 1, 2]$ at the beginning.

Then value $3$ is added to node $2$. It propagates and value -$3$ is added to it's sons, node $4$ and node $5$. Then it cannot propagate any more. So the values of the nodes are $[1, 5, 1,  - 2,  - 1]$.

Then value $2$ is added to node $1$. It propagates and value -$2$ is added to it's sons, node $2$ and node $3$. From node $2$ it propagates again, adding value $2$ to it's sons, node $4$ and node $5$. Node $3$ has no sons, so it cannot propagate from there. The values of the nodes are $[3, 3,  - 1, 0, 1]$.

You can see all the definitions about the tree at the following link: http://en.wikipedia.org/wiki/Tree_(graph_theory)