题目描述

富丽堂皇的罗兹瓦尔宅邸拥有成千上万间房间,宅邸内有一对双胞胎女仆雷姆和拉姆负责整个宅邸的家务。
Dl1AKJ.jpg

雷姆:
鬼族,罗兹瓦尔宅邸工作的双胞胎女仆的妹妹,特征是蓝发与右刘海。
虽然外貌与姐姐几乎一样,但是家务万能。

Dl1Fv4.jpg

拉姆
鬼族,罗兹瓦尔宅邸工作的双胞胎女仆的姐姐,特征是红发与左刘海。
不擅长料理,对罗兹瓦尔绝对忠诚与爱慕,拥有操纵风的能力。

由于女仆每天要进出房间打扫,所以一些房间的钥匙交由蕾姆和拉姆保管。雷姆和拉姆刚进宅邸的时候,所有这些钥匙都由雷姆保管。最开始雷姆保管着$n$把钥匙,第$i$把钥匙$(1\leq i \leq n)$用$i$表示。而作为宅邸的主人罗兹瓦尔,会让钥匙在雷姆和拉姆之间轮流保管,具体地说,罗兹瓦尔会告诉雷姆和拉姆一个秘密整数$x(1\leq x\leq n)$,表示让持有第$x$把钥匙的女仆将它交给另一个女仆(如果是雷姆持有,就把它交给拉姆,反之亦然)。雷姆和拉姆都对主人保持着绝对的忠诚,一定会按主人所说的做,并为主人保守这个秘密。

罗兹瓦尔宅邸里面还有一个充满魔力的房间作为禁书库。禁书库由碧翠丝管理着。

Dl1Er9.jpg
碧翠丝
大精灵,外表是十一二岁的可爱萝莉,金色的长螺旋状卷发,穿着华丽的礼服。
罗兹瓦尔宅邸禁书库的图书管理员,自称贝蒂。

贝蒂为了让禁书库更加安全,用魔法制作了一扇需要两把钥匙才能打开的门,其中一把由雷姆保管,另一把由拉姆保管。并且这两把钥匙不是固定的,会随着雷姆和拉姆所保管的钥匙的不同而改变。具体地说,如果这两把钥匙的代号分别为$p$和$q$,需要满足以下条件才能打开禁书库的门:

  • $p \leq q$
  • 这两把钥匙不由同一个人保管
  • 在$p$最大的前提下,$q$要最小。

486君现在居住在宅邸中,并且因为一次偶然的巧合知道了这个秘密,为了能够自由地进入禁书库与贝蒂幽会,他把所有罗兹瓦尔的秘密数字都记录下来,并且记录了后立刻就告诉了你。这样,每当他想进入禁书库幽会时,就会来询问你禁书库的钥匙是哪两把。作为工具人兼打工人的你需要在每次486君询问时正确地计算并告诉他禁书库的钥匙。


输入格式

输入第一行包含两个整数$n$和$m(1 \leq n, m\leq 2 \times 10^5)$,分别代表着雷姆最开始保管的钥匙数量以及486君找你的次数。
接下来输入$m$行,每行开头包含一个单词,一定是“MOVE”或“ASK”当中的其中一个(不含双引号),表示486君告诉你罗兹瓦尔的秘密数字或者询问你禁书库的钥匙。
如果是MOVE,那么该行后面还会有个整数$x(1\leq x \leq n)$(单词与整数之间有一个空格),表示486君告诉你罗兹瓦尔的秘密数字。
如果是ASK,表示486君询问你禁书库的钥匙。你需要回答两个整数。


输出格式

对于每个ASK询问,你需要输出一行包含两个整数$p,q(p \leq q)$,表示禁书库的两把钥匙,两个整数之间用一个空格隔开。
如果找不到这样的两把钥匙(比如说,钥匙全部由雷姆保管时),则输出0 0(两个零之间有一个空格),表示告诉486禁书馆当前无法进入。


样例数据

输入

4 6
MOVE 4
ASK
MOVE 4
ASK
MOVE 2
ASK

输出

3 4
0 0
2 3

备注

总共有4把钥匙,最开始全部由雷姆保管。
MOVE 4后:
雷姆:{1,2,3}
拉姆:{4}
所以ASK答案为3 4
再次MOVE 4:
雷姆:{1,2,3,4}
拉姆:{}
全部钥匙仅有一人保管,找不到禁书库钥匙,所以ASK答案为0 0。
MOVE 2后
雷姆:{1,3,4}
拉姆:{2}
所以ASK答案为2 3。


信息

时间限制: 1s
内存限制: 128MB
评测模式: Normal

导航

比赛介绍
比赛排名
数据统计
评测状态
答疑平台
打印服务