383_C. Propagating tree
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 ai. 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 a1, a2, ..., an (1 ≤ ai ≤ 1000). Each of the next n–1 lines contains two integers vi and ui (1 ≤ vi, ui ≤ n), meaning that there is an edge between nodes vi and ui.

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.

Examples

Input

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


Output

3
3
0

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)
```python
class BIT():
    """区間加算、一点取得クエリをそれぞれO(logN)で応えるデータ構造を構築する
    add: 区間[begin, end)にvalを加える
    get_val: i番目(0-indexed)の値を求める
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def get_val(self, i):
        i = i + 1
        s = 0
        while i <= self.n:
            s += self.bit[i]
            i += i & -i
        return s

    def _add(self, i, val):
        while i > 0:
            self.bit[i] += val
            i -= i & -i

    def add(self, i, j, val):
        self._add(j, val)
        self._add(i, -val)


from collections import deque
import sys
input = sys.stdin.readline


def eular_tour(tree: list, root: int):
    """頂点に対するオイラーツアーを行う
    posの部分木に区間[begin[pos], end[pos])が対応する
    """
    n = len(tree)
    res = []
    begin = [-1] * n
    end = [-1] * n
    visited = [False] * n
    visited[root] = True
    q = deque([root])
    while q:
        pos = q.pop()
        res.append(pos)
        end[pos] = len(res)
        if begin[pos] == -1:
            begin[pos] = len(res) - 1
        for next_pos in tree[pos]:
            if visited[next_pos]:
                continue
            else:
                visited[next_pos] = True
                q.append(pos)
                q.append(next_pos)

    return res, begin, end

n, q = map(int, input().split())
init_cost = list(map(int, input().split()))
info = [list(map(int, input().split())) for i in range(n-1)]
query = [list(map(int, input().split())) for i in range(q)]

tree = [[] for i in range(n)]
for i in range(n-1):
    a, b = info[i]
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)

res, begin, end = eular_tour(tree, 0)
even_res = []
odd_res = []
for i in range(len(res)):
    if i % 2 == 0:
        even_res.append(res[i])
    else:
        odd_res.append(res[i])

even_bit = BIT(len(even_res))
odd_bit = BIT(len(odd_res))

for i in range(q):
    if query[i][0] == 1:
        _, pos, cost = query[i]
        pos -= 1
        if begin[pos] % 2 == 0:
            even_bit.add(begin[pos] // 2, (end[pos] + 1) // 2, cost)
            odd_bit.add(begin[pos] // 2, end[pos] // 2, -cost)    
        else:
            odd_bit.add(begin[pos] // 2, end[pos] // 2, cost) 
            even_bit.add((begin[pos] + 1) // 2, end[pos] // 2, -cost) 
    else:
        _, pos = query[i]
        pos -= 1
        if begin[pos] % 2 == 0:
            ans = even_bit.get_val(begin[pos] // 2)
        else:
            ans = odd_bit.get_val(begin[pos] // 2)
        print(ans + init_cost[pos])
```