Xiao R's favourite operator in coding is the bitwise XOR operator, because his name is very similar to it (XiaO R)! He has also recently learned about Trees and the Fibonacci Sequence. Xiao R has come up with a problem combining all of that, and he is asking for you to help him solve it!

Consider a tree with ~N~ nodes labelled from ~1...N~, and an isolated node ~0~, with no edges connected to it. For every ~0 \leq i \leq N~, the value of node ~i~ is denoted as ~c_i~, which is initially set to ~0~. There are two types of operations you can perform on the tree:

1. Modify operation: M u x y

   • Temporarily add an edge between node ~0~ and node ~u~.
   • Root the entire tree at node ~0~.
   • For every node ~i~, calculate a secondary value ~s_i~ such that:
     • ~s_0 = x~
     • ~s_u = y~
     • For all other nodes ~i~: ~s_i = s_{p_i} \oplus s_{p_{p_i}}~, where ~p_i~ is the parent of ~i~ in the rerooted tree.
   • For every ~0 \leq i \leq N~, update ~c_i \leftarrow c_i + s_i~.
   • Remove the temporary edge between node ~0~ and node ~u~.

2. Query operation: Q v

   • Output the current value of ~c_v~.

Write a program that given the tree, processes ~Q~ operations.

Note: ~\oplus~ is the bitwise XOR operator.

Constraints

~2 \leq N, Q \leq 2 \cdot 10^5~

~1 \leq a, b, u \leq N~

~0 \leq v \leq N~

~0 \leq x, y \leq 10^9~

Subtask 1 [30%]

~u = 1~ for all modify operations.

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line will contain two space-separated integers ~N~ and ~Q~.

The next ~N-1~ lines will contain two space-separated integers ~a~ and ~b~, indicating an edge connecting nodes ~a~ and ~b~.

The next ~Q~ lines each contain an operation in the format described above.

Output Specification

For each query operation, output the answer on its own line.

Sample Input

5 4
3 4
2 1
5 3
1 3
M 1 6 5
Q 3
M 3 8 3
Q 0

Sample Output

3
14

Explanation for Sample

For the first modify operation, the rerooted tree is as follows:

The secondary values of nodes ~0~, ~1~, and ~3~ are: ~s_0 = 6~, ~s_1 = 5~, ~s_3 = s_{p_3} \oplus s_{p_{p_3}} = s_1 \oplus s_0 = 3~.

The value of ~c_0~ is now 6, and the value of ~c_3~ is now ~3~, which is the output for the first query operation.

For the second modify operation, the rerooted tree is as follows:

The secondary value of node 0 is: ~s_0 = 8~.

The value of ~c_0~ is now 14, which is the output for the second query operation.