思路:并查集

考虑将$n$个实验站看成图上的$n$个节点。那么

• 每次在两个实验站之间建立链路，相当于在对应的节点之间连一条边
• 每次查询一个实验站可以向左和向右到达的最远实验站，这启发我们并查集合并时需要维护两个值，一个合并时总是指向值更小的，一个合并时总是指向值更大的。即维护集合最大最小值

具体的，假设要合并的两个集合为$x,y$ , 显然有$max(x \cup y) = max(max(x) , max(y))$,最小值同理. 所以要在合并集合的过程中维护最值。我们只需要取两者的最值即可完成计算。

题目内容

有一排共 $n$ 个实验站，从左到右依次编号为 $1, 2, \dots, n$。初始时各实验站之间没有直接链路。

工程师会进行 $T$ 次操作，每次操作的类型和含义如下（用单字符表示）：

• L x：尝试在编号为 $x$ 的实验站与它左侧的实验站之间建立一条链路。若 $x$ 已是最左端，或该链路已存在，则本次操作无效。
• R x：尝试在编号为 $x$ 的实验站与它右侧的实验站之间建立一条链路。若 $x$ 已是最右端，或该链路已存在，则本次操作无效。
• Q x：查询从编号为 $x$ 的实验站出发，经过已有的链路连通，能够抵达的最左端实验站编号和最右端实验站编号。

你需要依次处理这些操作，并在每次遇到 Q 操作时输出对应的结果。

约束：实验站数量 $n$ 不超过 $10^4$，操作次数 $T$ 不超过 $200$，所有操作中的编号 $x$ 满足 $1 \le x \le n$。

输入描述

第一行包含两个整数 $n$ 和 $T$，用空格分隔。 接下来 $T$ 行，每行包含一个字符和一个整数，分别表示操作类型和操作的实验站编号 $x$。字符为 L、R 或 Q，与整数之间用空格分隔。

输出描述

对于每个 Q 操作，输出一行两个整数，用空格分隔，分别表示从该实验站出发能到达的最左端编号和最右端编号。

样例1

输入

3 1
Q 2

输出

2 2

说明

初始时没有任何链路，实验站 2 只能到达自身，因此最左端和最右端编号均为 2。

样例2

输入

5 5
L 2
R 2
Q 2
L 4
Q 3

输出

1 3
1 4

说明

首先执行 L 2，在实验站 2 和 1 之间建立链路，此时连通块包含 $\{1, 2\}$。 接着执行 R 2，连接实验站 2 和 3，连通块扩展为 $\{1, 2, 3\}$。查询 Q 2 时，得到最左端 1、最右端 3。 然后执行 L 4，连接实验站 4 和 3，连通块变为 $\{1, 2, 3, 4\}$。最后查询 Q 3，最左端仍为 1，最右端变为 4。

样例3

输入

5 6
L 1
R 5
L 3
L 3
Q 3
Q 1

输出

2 3
1 1

说明

L 1 因 $x=1$ 为最左端而无效。R 5 因 $x=5$ 为最右端而无效。 L 3 成功连接实验站 3 和 2，形成连通块 $\{2, 3\}$。第二个 L 3 因链路已存在而无效。 查询 Q 3 返回 $2$ 和 $3$。查询 Q 1 时实验站 1 未连接任何链路，仅能到达自身，输出 $1$ $1$。