Manobras no pátio

Time limit: 5000 msMemory limit: 256 MB

Há $N$ vagões, numerados de 1 a $N$ . Inicialmente, cada vagão forma sozinho um trem. Cada trem tem uma ordem da esquerda para a direita. Execute os comandos:

J x y: se $x$ e $y$ estiverem em trens diferentes, una o trem inteiro que contém $x$ ao trem inteiro que contém $y$ , colocando o primeiro à esquerda do segundo e preservando a ordem interna de ambos. Se já estiverem no mesmo trem, não faça nada. Os vagões $x$ e $y$ não precisam estar nas extremidades.
C x: separe o trem imediatamente antes do vagão $x$ . A parte à esquerda e a parte que começa em $x$ tornam-se trens independentes, preservando suas ordens. Se $x$ já for o primeiro vagão, não faça nada.
V x: inverta a ordem de todo o trem que contém $x$ .
Q x: informe os vizinhos imediatos à esquerda e à direita de $x$ no trem atual.

As operações referem-se sempre aos identificadores originais dos vagões, que nunca mudam.

Input

A primeira linha contém $N$ e $Q$ . As próximas $Q$ linhas contêm os comandos descritos acima.

$1 \le N,Q \le 200\,000$ ;
.

Output

Para cada comando Q x, imprima dois inteiros: o vizinho à esquerda e o vizinho à direita. Use 0 para uma extremidade sem vizinho.

Samples

Sample 1

Input

Output

4 2
0 2
2 4

Após as três junções, o trem é 1,2,3,4; após a inversão, é 4,3,2,1. O corte deixa 4 separado de 3,2,1. A última junção forma 3,2,1,4.