You are given a tree with ~n~ vertices, rooted at vertex ~1~. Each vertex ~i~ has an integer value ~a_i~. You must process ~q~ queries of two types:

• 1 v x: add ~x~ to the value of every vertex in the subtree of ~v~ (including ~v~ itself)
• 2 u: output the current value of vertex ~u~

Use the enter/exit Euler tour from Pondo Euler Tour. The subtree of ~v~ occupies the contiguous range ~[\mathrm{first}[v], \mathrm{last}[v]]~ on that tour, so a subtree add is a range add and a vertex query is a point query at ~\mathrm{first}[u]~.

The Fenwick tree below supports range add and point query. range_add(l, r, x) adds ~x~ to every index in ~[l, r]~ (inclusive, 0-indexed). point(i) returns the value at index ~i~.

class Fenwick:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, i, delta):
        while i <= self.n:
            self.bit[i] += delta
            i += i & -i

    def prefix(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def range_add(self, left, right, delta):
        self.add(left + 1, delta)
        self.add(right + 2, -delta)

    def point(self, i):
        return self.prefix(i + 1)

Input

The first line contains two integers ~n~ and ~q~.

The second line contains ~n~ integers ~a_1, a_2, \ldots, a_n~, the initial values of the vertices.

Each of the next ~n - 1~ lines contains two integers ~u~ and ~v~, denoting an undirected edge between ~u~ and ~v~.

Each of the next ~q~ lines describes a query and is one of the following:

• 1 v x: add ~x~ to every vertex in the subtree of ~v~
• 2 u: query the value of vertex ~u~

Vertices are numbered ~1~ through ~n~. The edges form a tree.

Output

For each query of type 2, print a line containing the current value of that vertex.

Constraints

• ~1 \le n, q \le 10^5~
• ~1 \le u, v \le n~
• ~-10^9 \le a_i, x \le 10^9~

Example 1

Input

8 9
0 0 0 0 0 0 0 0
1 2
2 3
2 4
1 5
5 6
6 7
6 8
1 2 10
2 3
2 5
1 1 5
2 3
2 7
1 6 -3
2 7
2 1

Output

10
0
15
5
2
5

Explanation

The tree, rooted at ~1~, looks like this:

      1
     / \
    2   5
   / \   \
  3   4   6
         / \
        7   8

• Adding ~10~ to the subtree of ~2~ changes vertices ~2, 3, 4~.
• Vertex ~3~ is then ~10~, and vertex ~5~ is still ~0~.
• Adding ~5~ to the subtree of ~1~ changes every vertex.
• Vertex ~3~ becomes ~15~ and vertex ~7~ becomes ~5~.
• Adding ~-3~ to the subtree of ~6~ changes vertices ~6, 7, 8~, so vertex ~7~ becomes ~2~.
• Vertex ~1~ is ~5~.

Example 2

Input

5 7
1 2 3 4 5
1 2
1 3
3 4
3 5
2 1
1 3 10
2 4
2 2
1 1 -1
2 5
2 1

Output

1
14
2
14
0