Given a tree with $n$ vertices numbered from $1$ to $n$. Each vertex $i$ has an initial value $W_i$. You need to perform two types of queries:
- add(v, x): Increase the value for all neighbors of v with x. It is guaranteed that $1 \leq v \leq n$ and $1 \leq x \leq 1000$.
- get(v): Print the value of vertex v ($1 \le v \le n$).
Input
The first line of input contains the number of vertices ($1 \leq n \leq 10^5$).
The following line contains $n$ integers $W_i$ ($1 \leq W_i \leq 1000$) separated by a whitespace with the initial values of the vertices.
The following $n-1$ lines contain two integers $u$ and $v$ ($1 \leq u, v \leq n$, $u \neq v$) separated by a whitespace, indicating that there is an edge between vertices $u$ and $v$.
The next line contains the number of queries $q$ ($1 \leq q \leq 2 \times 10^5$).
The following $q$ lines contain the description of the queries, in the format explained above.
Output
For each query of type $2$, print the value of the vertex $v$ in each case.
Sample test(s)
Input
4
1 2 3 4
1 2
1 3
1 4
5
1 1 3
2 1
2 2
2 3
2 4
Output
1
5
6
7
Input
4
1 2 3 4
1 2
1 3
1 4
6
1 2 3
2 1
2 2
2 3
1 1 4
2 4
Output
4
2
3
8