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 300\,000~
~1 \le M \le 100\,000~
~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