In Nirma, each employee is given an ID starting from 1 to N.

Each employee has some initial salary which is given to you.

Employee A is said to be the captain of employee B if A is the ancestor of B.

Read more about ancestor here: link

Now, you have to solve Q queries of following 2 types:

1) 1 x : In this query, you need to output the sum of salary of all the employees under x and including x.

2) 2 x : In this query, first you need to find the minimum salary of all the employees under x and including x. Let's denote it by min1. Then, you need to find minimum of min1 and 999. Let's denote it by min. Now, you need to increase the salary of all the employees under x and including x by min.

Note:

1) Every employee will have at-most one immediate captain.

2) Given Tree is rooted at ID 1.

Use of Fast I/O is recommended.

See Sample test-case for more understanding.

Input format:

First line consists of two numbers N denoting number of employees.

Next N-1 lines consists of 2 numbers a and b denoting there is an edge between a and b.

Next line consists of N integers denoting the intial salaries of all the employees.

Next line consists of Q denoting number of queries.

Next Q lines will be of any of the 2 types of queries mentioned in the problem.

Output format:

For every query of type 1, output the required answer.

Constraints:

1 <= N <= 3 * 10^5

1 <= Q <= 10^5

1 <= a, b <= N

1 <= salary[i] <= 500

1 <= x <= N