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^{9}
1 ≤ x ≤ N
1 ≤ y ≤ 10^{9}
1 ≤ u ≤ N
1 ≤ v ≤ N