题目描述

空の数列 $A$ があります。
クエリが $Q$ 個与えられるので、与えられた順番に処理してください。
クエリは次の $3$ 種類のいずれかです。

• 1 x ： $A$ に $x$ を追加する。
• 2 x k ： $A$ の $x$ 以下の要素のうち、大きい方から $k$ 番目の値を出力する。($k$ は $\bf{5}$ 以下)
  ただし、$A$ に $x$ 以下の要素が $k$ 個以上存在しないときは -1 と出力する。
• 3 x k ： $A$ の $x$ 以上の要素のうち、小さい方から $k$ 番目の値を出力する。($k$ は $\bf{5}$ 以下)
  ただし、$A$ に $x$ 以上の要素が $k$ 個以上存在しないときは -1 と出力する。

输入格式

入力は以下の形式で標準入力から与えられる。

$Q$ $\text{query}_1$ $\text{query}_2$ $\vdots$ $\text{query}_Q$

$i$ 番目のクエリ $\text{query}_i$ では、まずクエリの種類 $c_i$ ($1,2,3$ のいずれか) が与えられる。
$c_i=1$ の場合は $x$ が追加で与えられ、$c_i=2,3$ の場合は $x,k$ が追加で与えられる。

すなわち、各クエリは以下に示す $3$ つの形式のいずれかである。

$1$ $x$

$2$ $x$ $k$

$3$ $x$ $k$

输出格式

$c_i=2,3$ を満たすクエリの個数を $q$ として $q$ 行出力せよ。
$j(1\leq\ j\leq\ q)$ 行目では $j$ 番目のそのようなクエリに対する答えを出力せよ。

题目大意

题意简述

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

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

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

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

数据范围

$1\le Q\le2\times10^5$。

$1\le x\le10^{18}$。

$1\le k\le5$。

所有输入均为整数。

输入格式

第一行包含一个整数 $Q$，接下来 $Q$ 行每行一次操作。 具体询问输入参考题意简述。

输出格式

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

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\leq\ Q\ \leq\ 2\times\ 10^5$
• $1\leq\ x\leq\ 10^{18}$
• $1\leq\ k\leq\ 5$
• 入力は全て整数である

Sample Explanation 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$ です。