Solved!
Difficulty: Div2D-Div2E

Note: this problem is drafted on 2019/7/30 by XGN and not released. It's now released on 2022/1/2 by Zzzyt under his permission.

Statement

Yuqi has an rooted indexed tree T of N nodes indexed from 1 to N. The node 1 is the root. Now on each node there is an enemy with Health Point(HP) v_i and Yuqi has to defeat them.
He can cast several kinds of magic:

• Magic Kind 1: given a b increase the HP in the subtree of node a by b. (1\leq a\leq N,0\leq |b|\leq 10^9)

• Magic Kind 2: given a b increase the HP of node a by b. (1\leq a\leq N,0\leq |b|\leq 10^9)

• Magic Kind 3: given a if a is in the Blacklist remove it, otherwise add it into the blacklist. (1\leq a\leq N)

• Magic Kind 4: given a.tell Yuqi the HP of node a. (1\leq a\leq N)

Nodes in Blacklist's HP will not be affected by any other magic until it's removed.
Now he gives you the list of magic to proceed. You need to proceed them in order. Note that the enemy's HP can be negative at any moment without dying.

Input

The first line contains one integer N. (1\leq N\leq 10^5)
The next n-1 lines each contains two numbers x y (1\leq x,y\leq N) indicating an edge.
The next line contains N integers, the array V. (1\leq V_i\leq 10^9)
The following line contains one integer q - the number of magic to proceed.(1\leq q\leq 10^5)
Then next q lines can be:

• 1 a b Magic Kind 1

• 2 a b Magic Kind 2

• 3 a Magic Kind 3

• 4 a Magic Kind 4

Output

For each magic 4, print the answer in a line.

Example

Input

4
1 2
1 3
2 4
1 2 3 4
7
3 3
1 1 1
2 2 2
4 1
4 2
4 3
4 4

Output

2
4
3
5

Solution

By XGN:

This problem has been included in Hackerearth Data Structures and Algorithms coding challenge