시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 8 2 2 25.000%

문제

Consider a multiset $A$ consisting of $n$ elements: $a_1, a_2, \ldots, a_n$.

Let us define two types of operations which can be performed on this multiset:

  1. Given $x_i$, you have to print the number which will be $x_i$-th element if we sort the multiset in non-decreasing order.
  2. Given $x_i$, you have to subtract $x_i$ from all the elements of $A$ which are strictly greater than $x_i$.

Your task is to perform $q$ given operations in the given order and output the results of all operations of the first type.

입력

The first line contains two integers $n$ and $q$: the size of the multiset $A$ and the number of queries ($1 \le n \le 10^5$, $1 \le q \le 10^6$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$): the elements of $A$.

Each of the next $q$ lines describes a single operation. An operation is given as two integers $t_i$ and $x_i$: the type and the parameter of the operation. It is guaranteed that $t_i \in \{1, 2\}$. If $t_i = 1$, then $1 \le x_i \le n$. If $t_i = 2$, then $1 \le x_i \le 10^9$.

It is guaranteed that there is at least one operation of type $1$.

Please note that elements of $A$ are given in arbitrary order.

출력

For each operation of the first type, output the $x_i$-th element in non-decreasing order. Separate the answers with line breaks.

예제 입력 1

4 5
1 5 6 12
2 5
1 1
1 2
1 3
1 4

예제 출력 1

1
1
5
7

예제 입력 2

5 4
1 10 5 4 2
2 1
1 5
2 3
1 2

예제 출력 2

9
1

예제 입력 3

3 2
3 2 1
2 10000
1 3

예제 출력 3

3