配点 : $400$ 点

問題文

空の数列 $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 と出力する。

制約

• $1\leq Q \leq 2\times 10^5$
• $1\leq x\leq 10^{18}$
• $1\leq k\leq 5$
• 入力は全て整数である

入力

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

$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$ 番目のそのようなクエリに対する答えを出力せよ。

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