시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 13 4 4 30.769%

## 문제

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