Veshy has a box with $N$ items, the $i$th of which has a "goodness" of $g_i$ on Veshy's standards. Over a period of $M$ minutes, one of two events may occur. On the $i$th minute, either Veshy's standards have changed and the $a_i$th item's "goodness" has changed to $b_i$, or he wants to know the goodness of the $c_i$th best item in the subarray of items, $g_{l_i},g_{l_i+1},\dots ,g_{r_i}$.

It is recommended that Python users use PyPy instead.

Constraints

In all subtasks,
$1\le N\le 300000$
$1\le M\le 100000$
$0\le g_i,b_i\le 20$
$1\le a_i,l_i,r_i,c_i\le N$

Subtask 1 [10%]

$N\le 100$

Subtask 2 [30%]

$0\le g_i,b_i\le 1$

Subtask 3 [60%]

No additional constraints.

Input Specification

The first line contains two space-separated integers, $N$ and $M$.
The next line contains $N$ integers, the $i$th of which being $g_i$.
$M$ lines follow, each of which are either in the form:
1 a b - the $a_i$th item now has goodness $b_i$
2 l r c - Veshy wants to know the goodness $c_i$th best item in the subarray of items: $l,l+1,\dots ,r$

Output Specification

For each query, output the goodness of the $c_i$th best item in the subarray of items. It is guaranteed that there are at least $c_i$ items in the subarray.

Sample Input

5 5
3 15 19 7 14
2 2 4 2
1 2 9
2 1 2 2
1 5 17
2 1 5 3

Sample Output

15
3
9