A long time ago, in the not-so-distant LCT (land of the carrot trees), where carrots grow on trees, lived a magical carrot. In this magical land, there were $N$ cities numbered $1,2,\dots ,N$, connected with $N-1$ roads, with no cycles. Over the course of $Q$ days, some interesting things happened to the roads:

• A x y z: A new road of durability $z$ is built between cities $x$ and $y$
• R x y: The road between cities $x$ and $y$ is destroyed by a rampaging rabbit (it is guaranteed to exist prior to the operation)
• Q x y: The eccentric king demanded to know the $XOR$ of the durability of all roads on the path between cities $x$ and $y$

It is guaranteed that there will be at most one path between any two cities at any point in time.

Can you help the people of LCT by implementing a program to simulate these events?

Constraints

For all subtasks:

The durability of a path will be a positive integer in the range $[1,{10}^6]$.

Subtask 1 [20%]

$1\le N\le 1000$

$1\le Q\le 1000$

Subtask 2 [80%]

$1\le N\le {10}^5$

$1\le Q\le {10}^5$

Input Specification

The first line of input will have two integers, $N$ and $Q$.
The next $N-1$ lines will contain three integers, $a_i,b_i,c_i$, indicating there is a road of durability $c_i$ between cities $a_i$ and $b_i$.
The next $Q$ lines will each contain a valid query.

Output Specification

For each Q query, print the answer to it on a new line. If the two cities are not connected, output -1.

Sample Input 1

5 4
1 2 3
2 4 5
3 5 6
2 3 8
R 3 2
A 3 1 6
Q 5 4
Q 3 2

Sample Output 1

6
5

Sample Input 2

6 8
1 2 3
3 4 5
4 5 6
4 1 8
6 1 4
Q 6 5
Q 3 2
R 4 3
R 4 1
A 1 3 8
Q 3 2
Q 4 5
Q 6 1

Sample Output 2

10
14
11
6
4