Migrated from Lutece 2866 Bounce!

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Kanade 十分喜欢《涂鸦跳跃》（Doodle Jump）这款游戏。这款游戏十分简单，需要玩家通过重力感应操作让一只名为 The Doodler 的四脚动物（可能是貘）不停地往上跳跃，以取得更高的分数。这款游戏正因为操作简单，耐玩性高，所以受到了大量好评。

Kanade 最近在复刻这款游戏，她起名为「Angel Bounce!」，我们就叫它「Bounce!」 好了。

与 Doodle Jump 不同，「Bounce! 」这款游戏的地图是横向的。玩家起初位于一条平行于 $x$ 轴的线段上，这条线段由 $n$ 条单位线段顺次相连而成。Kanade 将这 $n$ 条单位线段从左向右标号为 $1$ 到 $n$。

现在，Kanade 正在设计 Lunatic 难度的地图，起初这个地图只是一条平行于 $x$ 轴的线段 $[1,n]$，Kanade 对此地图有以下两个操作：

• A l r x，表示 Kanade 设置了两个断点 $x=l,x=r$，并将编号在 $[l,r]$ 内的所有单位线段沿 $y$ 轴正方向平移 $x$ 个单位长度。如果 $x=0$，则说明并没有移动，请忽略这次操作；
• C，表示 Kanade 进行了一次对 A 操作的撤销，撤销到上一次修改前的状态。

某些时候，Kanade 想知道，编号为 $p$ 的单位线段所在最长线段的左右两端的单位线段编号，用 B p 表示。

请帮助 Kanade 完成这些操作。

Input

第一行两个正整数 $n,T\ (2\le n\le 3\times 10^5,1\le T\le 2\times 10^5)$，$n$ 的意义如题目描述，$T$ 为操作个数；

接下来 $T$ 行，每行表示一个操作。对于 A 操作，保证 $1\le l<r\le n,|x|\le 10^4$，对于 B 操作，保证 $1\le p\le n$。对于 C 操作，保证有操作可以撤销。对于所有操作，保证所有出现的数字都为整数。

Output

对于每一个 B 操作，输出一行两个正整数，表示经过 $x=p$ 这一位置的最长线段的左右端点位置。

Samples

10 7
A 2 6 1
A 3 5 2
B 5
B 8
C
B 1
B 3

3 5
7 10
1 1
2 6

Note

我们借用集合符号表示一段线段。

第一次操作后，得到三段线段：$\{1\},\{2,3,4,5,6\},\{7,8,9,10\}$；

第二次操作后，得到五段线段：$\{1\},\{2\},\{3,4,5\},\{6\},\{7,8,9,10\}$；

过编号为 $5$ 的最长线段为 $\{3,4,5\}$，最左端单位线段编号为 $3$，最右端为 $5$，过编号为 $8$ 的最长线段为 $\{7,8,9,10\}$，最左端的单位线段编号为 $7$，最右端为 $10$；

撤销第二次操作，回到第二次操作前，即第一次操作后的状态；

过编号为 $1$ 的最长线段为 $\{1\}$，最左端和最右端的单位线段编号均为 $1$，过编号为 $3$ 的最长线段为 $\{2,3,4,5,6\}$，最左端单位线段编号为 $2$，最右端为 $6$。

Resources

The 20th UESTC Programming Contest Preliminary