19497번 - Subtract if Greater! 다국어

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.