提示: 欢迎访问OurACM平台。
Problem 1962 新击鼓传花游戏

Accept: 165    Submit: 428
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

N个小朋友,编号为1..N,玩新击鼓传花游戏。游戏由老师来主持,老师将下达M条命令,命令包含以下三种,

L k,让将当前游戏中剩余的小朋友中,编号第k小的小朋友离开游戏。

R x,让编号为x的小朋友重新回到游戏中,如果编号为x的小朋友已经在游戏中,那么不做任何变化。

Q k,查询并输出当前剩余小朋友中,编号第k小的小朋友的编号。

Input

第一行两个整数N, M(1<=N, M<=500,000),表示小朋友的人数和老师命令的条数。接下来m行,每行按指定格式给出一条命令,输入数据保证k不大于当前剩余的小朋友数量,而1<=x<=N。

Output

对测试数据中的查询语句,输出一行,表示当前编号第k小的小朋友编号。

Sample Input

5 5 L 1 L 1 Q 1 R 1 Q 1

Sample Output

3 1

Source

Contest for 2010 lecture I

Submit  Back  Status  Discuss