序列查询

题目描述

我们有一个空序列 $A$。

给定 $Q$ 个查询,请按顺序处理它们。

每个查询是以下三种类型之一。

1 x : 将 $x$ 插入 $A$。

2 x k : 在 $A$ 中小于等于 $x$ 的元素中,输出第 $k$ 大的值。($k$ 不超过 $\mathbf{5}$)

如果 $A$ 中小于等于 $x$ 的元素不足 $k$ 个,则输出 -1。

3 x k : 在 $A$ 中大于等于 $x$ 的元素中,输出第 $k$ 小的值。($k$ 不超过 $\mathbf{5}$)

如果 $A$ 中大于等于 $x$ 的元素不足 $k$ 个,则输出 -1。

输入格式

输入按以下格式从标准输入给出:

Q
query_1
query_2
⋮
query_Q

在第 $i$ 个查询 $\text{query}_i$ 中,首先给出查询类型 $c_i$(为 $1、2$ 或 $3$ 之一)。

如果 $c_i=1$,则额外给出 $x$;如果 $c_i=2, 3$,则额外给出 $x$ 和 $k$。

换句话说,每个查询以以下三种格式之一给出:

1 x

2 x k

3 x k

输出格式

输出 $q$ 行,其中 $q$ 是满足 $c_i=2,3$ 的查询数量。

第 $j$ 行 $(1 \le j \le q)$ 应包含第 $j$ 个此类查询的答案。

样例

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

处理完 $\text{query}_{1,2,3,4}$ 后,有 $A=(20,10,30,20)$。

对于 $\text{query}_{5,6,7}$,$A$ 中大于等于 $15$ 的元素为 $(20,30,20)$。

其中第 $1$ 小的值为 $20$;第 $2$ 小为 $20$;第 $3$ 小为 $30$。

数据范围

• $1 \le Q \le 2 \times 10^5$
• $1 \le x \le 10^{18}$
• $1 \le k \le 5$
• 输入中的所有值均为整数。