Pondo Subtree Add

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

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

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

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

1
14
2
14
0