In 2016, Jiayuan just learned about trees and was very happy. Now, she wants to solve the following problem:

Given a rooted tree (with root 1), there are two types of operations:

1. Mark operation: Mark a specific node (initially, only node 1 is marked, and all other nodes are unmarked. A node can be marked multiple times).
2. Query operation: Query the nearest marked ancestor of a given node (a node is considered an ancestor of itself).

Can you help her?

Input

The first line contains two positive integers $N$ and $Q$, representing the number of nodes and the number of operations, respectively.

The next $N - 1$ lines each contain two positive integers $u, v$ ($1 \le u, v \le n$), representing a directed edge from $u$ to $v$.

The next $Q$ lines are in the format "oper num". If oper is "C", it represents a mark operation. If oper is "Q", it represents a query operation.

Output

For each query operation, output a single positive integer representing the result.

Constraints

• For 30% of the data, $1 \le N, Q \le 1000$.
• For 70% of the data, $1 \le N, Q \le 10000$.
• For 100% of the data, $1 \le N, Q \le 100000$.

Examples

Input 1

5 5
1 2
1 3
2 4
2 5
Q 2
C 2
Q 2
Q 5
Q 3

Output 1

1
2
2
1