题目描述

翁老师给你一个空序列 $a$。同时有 $q$ 次操作，每次询问是以下三种之一：

• 1 x：向 $A$ 中插入元素 $x$。

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

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

输入格式

第一行包含一个整数 $q$，接下来 $q$ 行每行一次操作。

每行先输入一个整数 $op$ 代表操作类型。

• 若 $op=1$，则继续输入一个整数 $x$，代表将 $x$ 加入集合。
• 若 $op=2$，继续输入两个整数 $x,k$，含义如题目描述所示。
• 若 $op=3$，继续输入两个整数 $x,k$，含义如题目描述所示。

输出格式

输出一共输出若干行，对于操作 $2,3$，输出一个数表示答案。

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

20
20
30
-1
-1
1

样例 1 解释

经过前四次操作以后，序列 A = 20 10 30 20

• 第五次查询大于或等于 $15$ 第 $1$ 小的元素，因此输出了 $20$。
• 第六次查询大于或等于 $15$ 第 $2$ 小的元素，因此输出了 $20$。由于有两个 $20$，因此其中一个可以算作是大于等于 $15$ 的第 $2$ 小整数。
• 第七次查询大于或等于 $15$ 第 $3$ 小的元素，因此输出了 $30$。
• 第八次查询大于或等于 $15$ 第 $4$ 小的元素，由于不存在，因此输出了 $-1$。
• 第九次查询小于或等于 $100$ 第 $5$ 大的元素，小于等于 $100$ 的元素只有 $4$ 个，因此输出了 $-1$。
• 第十次给序列加入 $1$，此时序列 A = 20 10 30 20 1
• 第十一次查询小于或等于 $100$ 第 $5$ 大的元素，小于等于 $100$ 的元素有 $5$ 个，第五大的是 $1$，因此输出了 $1$。

提示

对于 $100\%$ 的数据满足

• $1\leq\ q\ \leq\ 2\times\ 10^5$
• $1\leq\ x\leq\ 10^{18}$
• $1\leq\ k\leq\ 5$