You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目内容

小美所在的国家有 $n$ 个城市，这 $n$ 个城市排成一列，按顺序编号为 $1,2,3,...,n$。然而，由于历史原因和地理条件等多种原因，这些城市之间并没有相互连接的铁路，导致交通十分不便。

为了改善这种情况，政府决定修建一些铁路来提高城市之间的交通效率。具体来说，政府计划在未来的 $T$ 天内进行一系列铁路建设工作。每一天，政府会进行如下操作之一：

• L x：在编号为 $x$ 的城市和其左边的城市之间修建一条铁路，以便两个城市之间的交通更加便利。如果 $x$ 已经位于最左边，或者 $x$ 和它左边的城市之间已经存在铁路，则该操作无效。
• R x：在编号为 $x$ 的城市和其右边的城市之间修建一条铁路，以便两个城市之间的交通更加便利。如果 $x$ 已经位于最右边，或者 $x$ 和它右边的城市之间已经存在铁路，则该操作无效。
• Q x：查询从编号为 $x$ 的城市出发，最远能够到达的向左和向右的城市的编号。

小美需要编写一段程序来模拟这一系列操作，并及时输出每个 Q x 操作的结果。通过这个程序，政府可以更加高效地规划城市之间的交通网络，从而促进经济和社会的发展。

输入描述

第一行输入两个正整数 $n$ ， $T$ ； 接下来 $T$ 行，每行输入形如题面中的其中一种。

$1\le n\le 10000$ ， $1\le T\le 200$ ， $1\le x\le n$

输出描述

对于每一个Q x 操作，输出一行两个正整数，分别表示 $x$ 往左边和往右边最远能到达的城市编号中间用空格隔开。

样例

输入

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

输出

2 2
1 2
1 3