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 a value \(V_i\) .

He can cast several kinds of magic:

• Magic Kind 1: given a,b increase the value 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 value 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 value of node a. (\(1\leq a\leq N\))

Nodes in Blacklist's value 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 value of any node can be negative at any moment.

Input Format

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 Format

For each magic 4, output the answer. 

Subtasks

The author will warmly give you some hints here. 

In some testcases, the tree is a chain.(ie. for each \(2\leq x\leq n\).,there exists an edge connecting x and x-1)

In some other testcases, the depth of the tree is 2 (ie. no edge connects two non-root element)