Roger was able to solve his problem based on tree last time, only because of your help. He has been doing good and is learning and practicing various problems on trees (as he likes solving problems on connected undirected acyclic graphs). This time he is stuck with a harder problem and has spent almost a week trying to solve this problem, with no efficient solution till now. But, he has you as his friend and he knows that only you can help him with your excellent programming skills.

You will be given an input in the form of a growing tree. ie; Initially you have a tree consisting only of vertex 1. At each step, the tree will grow. So next, vertex u will be connected to vertex 1, then vertex v will be connected to either vertex 1 or vertex u, and so on till you get a tree consisting of 'N' vertex. However, at any instant, while adding the vertexes you will be given a vertex 'x' (which is already present in the tree grown so far), and you will be asked to print the eccentricity of the given vertex x.

Let G be a graph and 'x' be a vertex of G.

The eccentricity of the vertex 'x' is the maximum distance from 'x' to any vertex present in G.

That is, e (x) = max {d (x, y) : y is in G}.

Of Course vertex y, should also be present in the tree, grown so far.

Along with the eccentricity, you should also print the vertex 'y'.

Please help Roger.

Input

The first line contains 'N' and 'M', where N = Number of nodes in the tree and M = Number of Queries.

Next M lines will either have an input of the type "U x y" or "Q x".

For the input of type "U x y",  you have to connect the vertex 'y' to the vertex 'x', where vertex 'x' is already present in the tree and vertex 'y' is the new vertex. Obviously, there will be (N - 1) inputs of the type "U x y".

Output

For each input of the type "Q x", you have to print the eccentricity of vertex 'x', followed by the vertex 'y'.

If there are multiple such 'y'. Print the smallest 'y'.

Example

Sample Input
5 8
Q 1
U 1 4
Q 1
U 4 2
U 1 5
U 5 3
Q 1
Q 2

Sample Output
0 1
1 4
2 2
4 3

Explanation

Initially, the tree has vertex 1.

Q 1   => Eccentricity of vertex 1 is 0.

U 1 4 => Connect vertex 4 to vertex 1.

Q 1   => Eccentricity of vertex 1 is 1.

U 4 2 => Connect vertex 2 to vertex 4.

U 1 5 => Connect vertex 5 to vertex 1.

U 5 3 => Connect vertex 3 to vertex 5.

Q 1   => Eccentricity of vertex 1 is 2. Vertex 2 and Vertex 3 both are at a distance of 2 from vertex 1. Print the smaller one.

Q 2   => Eccentricity of vertex 2 is 4.

CONSTRAINTS

1 <= N <= 10^5
N - 1 <= M <= 2*N
1 <= x, y <= N