Problem Description

There is a rooted tree $ T $ with $ N $ vertices, numbered from $ 1 $ to $ N $. Initially, vertex $ 1 $ is the root.

Among the $ N-1 $ edges, the $ i $-th edge connects vertex $ a_i $ and vertex $ b_i $.

Each vertex $ v $ has an integer array $ A_v $. Initially, all arrays are empty.

We will perform $ Q $ query operations on this rooted tree $ T $. There are three types of query operations, described as follows:

• 1 v x k ― For any vertex $ u $ in the subtree of vertex $ v $ (including $ v $ itself), add $ k $ values of $ x $ to $ A_u $.
• 2 v y z ― Count the number of values $ val $ in the array $ A_v $ that satisfy $ val $ $ xor $ $y\ \leq\ z$. Here, $ s $ $ xor $ $ t $ denotes the bitwise XOR of $ s $ and $ t $.
• 3 v ― Change the root to vertex $ v $.

You must write a program to process these queries in order.

Input Format

The input is given from the standard input in the following format:

$ N $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ $ : $ $ a_{N-1} $ $ b_{N-1} $ $ Q $ $ Query_1 $ $ Query_2 $ $ : $ $ Query_Q $

• Each $ Query_i $ is given in one of the formats 1 v x k, 2 v y z, or 3 v.

Output Format

For each query in the format 2 v y z, output the answer in the given order.

Sample Input and Output

Sample Input #1

4
1 2
1 3
3 4
14
1 1 1 1
1 2 2 1
1 3 3 1
2 1 0 4
2 2 1 3
2 4 3 2
3 4
1 3 3 1
1 4 4 1
1 1 1 1
1 2 2 1
2 1 0 4
2 2 1 3
2 4 3 2

Sample Output #1

1
2
2
4
5
2

Sample Input #2

1
11
1 1 4 1
1 1 14 2
1 1 10 4
1 1 8 8
1 1 12 16
1 1 2 32
1 1 6 64
1 1 0 128
2 1 0 10
2 1 10 10
2 1 8 10

Sample Output #2

237
190
190

Sample Input #3

1
11
1 1 0 1000000000
1 1 0 1000000000
1 1 0 1000000000
1 1 0 1000000000
1 1 0 1000000000
1 1 0 1000000000
1 1 0 1000000000
1 1 0 1000000000
1 1 0 1000000000
1 1 0 1000000000
2 1 0 2

Sample Output #3

10000000000

Sample Input #4

1
2
1 1 1 123
2 1 0 1073741823

Sample Output #4

123

Notes/Hints

Constraints

• All inputs are integers.
• $1\ \leq\ N\ \leq\ 1.4\ \times\ 10^5$
• $1\ \leq\ Q\ \leq\ 1.4\ \times\ 10^5$
• $1\ \leq\ a_i,\ b_i\ \leq\ N$ $(1\ \leq\ i\ \leq\ N-1)$
• $1\ \leq\ v\ \leq\ N$
• $0\ \leq\ x,\ y,\ z\ <\ 2^{30}$
• $1\ \leq\ k\ \leq\ 10^9$
• The given graph is a tree.

Sample Explanation 1

• In the first query, add one value $ 1 $ to $ A_1 $, $ A_2 $, $ A_3 $, and $ A_4 $.
• In the second query, add one value $ 2 $ to $ A_2 $.
• In the third query, add one value $ 3 $ to $ A_3 $ and $ A_4 $.
• In the fourth query, change the root from vertex $ 1 $ to vertex $ 4 $.
• In the fifth query, since $A_1\ =\ \{1\}$ and $ 1 $ $ xor $ $0\ =\ 1$, output the count of values $ 1 $ which is $ 1 $.
• In the sixth query, since $A_2\ =\ \{1,2\}$ and $ 1 $ $ xor $ $1\ =\ 0$, $ 2 $ $ xor $ $1\ =\ 3$, output the count of values $ 0 $ and $ 3 $ which is $ 2 $.
• In the seventh query, since $A_4\ =\ \{1,3\}$ and $ 1 $ $ xor $ $3\ =\ 2$, $ 3 $ $ xor $ $3\ =\ 0$, output the count of values $ 2 $ and $ 0 $ which is $ 2 $.
• Continue similarly for the remaining queries.

Sample Explanation 3

The output may not fit within a 32-bit integer type.

见题面 Input 部分

见题面 Output 部分