Veshy has a box with items, the th of which has a "goodness" of on Veshy's standards. Over a period of minutes, one of two events may occur. On the th minute, either Veshy's standards have changed and the th item's "goodness" has changed to , or he wants to know the goodness of the th best item in the subarray of items, .
It is recommended Python users use PYPY instead.
In all subtasks,
Subtask 1 [10%]
Subtask 2 [30%]
Subtask 3 [60%]
No additional constraints
The first line contains two space-separated integers, and .
The next line contains integers, the th of which being .
lines follow, each of which are either in the form:
1 a b - the th item now has goodness
2 l r c - Veshy wants to know the goodness th best item in the subarray of items:
For each query, output the goodness of the th best item in the subarray of items. It is guaranteed that there are at least items in the subarray.
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
15 3 9