You are given a tree with N nodes (numbered 1 to N). The tree is rooted at node 1. Each node has a value a_i stored in it.

You have to process 2 types of queries on the tree. There will be Q such queries.

• Type 1:
Format: 1 x y
Change the value of node x to y (a_x = y).


• Type 2:
Format: 2 x
Find the sum of value in nodes in subtree of node x and print it in new line.
A subtree of node x means that it is a tree with root x and contains all descendants of x.

Input Format:

• The first line is an integer N denoting the number of nodes in tree.
• Next N-1 lines contains 2 integers u and v separated denoting there is an edge between u and v.
• The next line contains N integers separated by space. The i^th number denotes a_i.
• The next line contains Q, the number of queries to process.
• Q lines follow. A single line denotes a single query, which has one of the following forms:
• 1 x y - Change the value of node x to y.
• 2 x - Print the sum of value in nodes in subtree of node x in new line.

Output Format:
For each query of type 2 print a single line containing the answer to the query.


Constraints:
1 ≤ N ≤ 2000
1 ≤ Q ≤ 2000
1 ≤ a_i ≤ 10⁹
1 ≤ x ≤ N
1 ≤ y ≤ 10⁹
1 ≤ u ≤ N
1 ≤ v ≤ N


Sample Input:
7
1 2
2 7
5 3
4 1
6 3
1 3
3 8 6 4 1 2 5
6
2 3
1 5 10
2 3
2 2
1 4 7
2 1

Sample Output:
9
18
13
41