2180 - 序列操作
Description

有一个空序列 A。给定 Q 次操作,每次询问是以下三种之一:

>`1 x`:向 A 中插入元素 x

>`2 x k`:输出 A 中所有 \le x 的元素中的第 k 大值。如果不存在输出 `-1`。

>`3 x k`:输出 A 中所有 \ge x 的元素中的第 k 小值。如果不存在输出 `-1`。


Input

第一行包含一个整数 Q,接下来 Q 行每行一次操作。

具体询问输入参考题意简述。


Output

对于操作 2,3,输出一个数表示答案。

Examples

Input

11
1 20
1 10
1 30
1 20
3 15 1
3 15 2
3 15 3
3 15 4
2 100 5
1 1
2 100 5

Output

20
20
30
-1
-1
1
Hint

>1\le Q\le2\times10^5

>1\le x\le10^{18}

>1\le k\le5

>所有输入均为整数。

样例1说明:

在处理了 \text{query}_{1,2,3,4} 之后,我们得到 A=(20,10,30,20)

对于 \text{query}_{5,6,7}A 大于或等于 15 的元素是 (20,30,20)

其中 1 -st最小值为 20 ; 2 -nd为 20 ; 3 -rd为 30


题目参数
Time Limit 1 second
Memory Limit 128 MB
提交次数 5
通过次数 1