Given a tree with n vertices numbered from 1 to n . Each vertex i has an initial value Wi . 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≤v≤n and1≤x≤1000 . - get(v): Print the value of vertex v (
1≤v≤n ).
Input
The first line of input contains the number of vertices (1≤n≤105 ).
The following line contains n integers Wi (1≤Wi≤1000 ) separated by a whitespace with the initial values of the vertices.
The following n−1 lines contain two integers u and v (1≤u,v≤n , u≠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≤q≤2×105 ).
The following q lines contain the description of the queries, in the format explained above.
Output
For each query of type
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