You are given a tree with N nodes (numbered 1 to N). The tree is rooted at node 1. Each node has a value ai 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 (ax = 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 ith number denotes ai.
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 ≤ ai ≤ 109
1 ≤ x ≤ N
1 ≤ y ≤ 109
1 ≤ u ≤ N
1 ≤ v ≤ N