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.