迷之容器

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

FF最近得到了一个神奇的容器。他可以不停地往这个容器里放入数字,如果刚放入的这个数字已存在于容器中,那么容器只会保留其中的一个。

现在FF又有了一个很蛋疼的想法,他在放入了若干个数字之后,想知道容器中第K小的数字是多少。

 

 

Input

 多组输入。

对于每组数据,初始时容器为空。

每组数据输入一个n(1 <= n <= 100000),代表有n次查询和放入操作。

接下来的n行,每行一个字符 c和数字x (-1000,000,000<= x <= 1000,000,000),用空格隔开。

c “ P ”,则表明FF要放入x,此时[-1000 000 000,1000 000 000]

 “Q”,则表明FF想知道容器中第x小的数是多少,若不存在则用 -1代表,此时x[1100000]

Output

 对于每次询问,输出一个数字代表答案。

Sample Input

4
P 1
Q 1
P -1
Q 2

Sample Output

1
1

Hint

 

Source

zmx