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 that Python users use PyPy instead.
Constraints
In all subtasks,
Subtask 1 [10%]
Subtask 2 [30%]
Subtask 3 [60%]
No additional constraints.
Input Specification
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:
Output Specification
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.
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
Comments