A Job for a Slicer

You are a slicer (hacker) on board of a rebel cruiser with the mission of freeing an essential ally of the Galactic Empire, but to do that, you have to get access to the main terminal using a special card. The terminal has an internal algorithmic problem and a couple of some input tests, which are daily randomly generated. The terminal expects to get the same output from its internal code and the card's code.

You have just a blank card and the statement for the algorithmic problem that must be solved to print the code on the card. The statement sounds like this:

You are given a rooted tree, where node 1 is the root. The tree has N nodes, and each node has an initial value of 0. You are also given Q queries of 3 types:

• 1 u v: add value v to all nodes in the subtree with root u;
• 2 x: print the value of node x;
• 3 r: make node r the new root of the tree.

Input Specification

The first line contains a single number N, which represents the number of nodes (2 ≤ N ≤ 100 000).

Each of the next N – 1 lines contains two numbers separated by a space: a and b, which means that there is an edge between node a and node b.

The next line contains a number Q, which represents the number of queries (1 ≤ Q ≤ 100 000).

Each of the next Q lines contains one of the following types of queries mentioned above:

• The first type of query contains three numbers separated by spaces. The first number is 1, which indicates it's the first type of query, the second number is u indicating the root of the subtree, and the third number is the value v that must be added to each node in the subtree (–1000 ≤ v ≤ 1000).
• The second type of query contains two numbers separated by spaces. The first number is 2, which indicates it's the second type of query, and the second number is x indicating the node whose value must be printed.
• The third type of query contains two numbers separated by spaces. The first number is 3, which indicates it's the third type of query, and the second number is r indicating the new root of the tree.

Output Specification

The output should contain a single number for each query of type 2 on a different line, indicating the value of node x.

Sample Input

1. 5
2. 1 2
3. 1 3
4. 3 4
5. 4 5
6. 10
7. 1 3 2
8. 3 3
9. 1 3 1
10. 3 4
11. 1 1 5
12. 2 1
13. 2 2 
14. 2 3
15. 2 4
16. 2 5

download as text file

Output for Sample Input

1. 6
2. 6
3. 3
4. 3
5. 3

download as text file

Explanation

As it can be seen here, the answer for the last five queries in order are 6, 6, 3, 3, 3.