题目描述

坎格鲁斯普雷给了你一个长度为 $n$ 的序列，你要支持以下三种操作：

1、将整个序列复制一份后加入到序列的末尾，例如，序列原为 $[2,3,4,3]$ ，进行操作 $1$ 后变成了 $[2,3,4,3,2,3,4,3]$ ；

2、在序列的末尾加入一个数 $x$ ，题目保证操作 $2$ 给出的 $x$ 严格单调递增，且最开始给出的 $x$ 大于一开始序列中的最大数；

3、查询序列中第 $k$ 大的数。

对于每个操作 $3$ ，你需要回答坎格鲁斯普雷的询问。若序列中的数不足 $k$ 个，那么输出 "-1" （不带引号）。

输入格式

输入第一行两个整数 $n$ , $q$ ,分别表示序列长度和操作数量。 $(1 \leq n,q \leq 2 \times 10^5)$

输入第二行 $n$ 个整数 $a_i$ ，表示一开始的序列。 $(1 \leq a_i \leq 10^9)$

接下来 $q$ 行，先一个整数 $op$ ,表示操作类型。若 $op=1$ ，则接下来没有多余的输入；若 $op=2$ ，则接下来一个整数 $x$ ，表示往序列末尾加入的数；若 $op=3$ ，则接下来一个整数 $k$ ，表示查询序列中第 $k$ 大的数。$(op \in \{1,2,3\},1 \leq x,k \leq 10^9)$

题目保证操作 $2$ 给出的 $x$ 严格单调递增，且最开始给出的 $x$ 大于一开始序列中的最大数。

输出格式

对于每个操作 $3$ ，输出一行一个整数，表示答案。若序列中的数不足 $k$ 个，那么输出 "-1" （不带引号）。

输入输出样例

输入 #1

5 8
4 7 1 3 5
3 4
3 6
1
2 9
3 4
1
2 11
3 2

输出 #1

3
-1
5
9

说明与提示

对于样例 #1:

一开始序列为 $[4,7,1,3,5]$ 。

操作 $4$ 之后序列为 $[4,7,1,3,5,4,7,1,3,5,9]$ 。

操作 $7$ 之后序列为 $[4,7,1,3,5,4,7,1,3,5,9,4,7,1,3,5,4,7,1,3,5,9,11]$ 。