Range Ordered Set Queries

You are given an array of n integers. Your task is to design a data structure that maintains the array (ordered sequence) and supports the following operations on any subarray (i.e. on an interval):

1. Given an integer x and a subarray defined by indices l and r, output the rank of x in that subarray. The rank is defined as the number of elements that are strictly less than x plus one. In other words, if the subarray sorted in increasing order is \(a_1, a_2, \ldots, a_k\), then the rank of x is \(\#\{a_i: a_i < x\}+1\).
2. Given indices l and r and an integer k, output the value of the element with rank \(k\) in the subarray. That is, when the elements in the subarray are sorted increasingly, output the element at the \(k\)-th position.
3. Update the value at a specified position in the array.
4. Given indices l and r and an integer x, output the predecessor of x in the subarray, i.e. the maximum element that is strictly less than x. If there is no such element, output \(-2147483647\).
5. Given indices l and r and an integer x, output the successor of x in the subarray, i.e. the minimum element that is strictly greater than x. If there is no such element, output \(2147483647\).

Note: For a value x, its rank is defined as \(\text{rank}(x) = \#\{y: y < x\} + 1\).

inputFormat

The first line contains two integers \(n\) and \(m\), representing the number of elements in the array and the number of operations, respectively.

The second line contains \(n\) integers representing the initial array.

The following \(m\) lines each represent an operation. Each operation begins with an integer indicating the type:

• 1 l r x: Query the rank of x in the subarray from index l to r (1-indexed).
• 2 l r k: Query the element with rank k in the subarray [l, r].
• 3 pos newVal: Update the element at position pos to newVal.
• 4 l r x: Query the predecessor of x in the subarray [l, r].
• 5 l r x: Query the successor of x in the subarray [l, r].

Indices are 1-indexed.

outputFormat

For each query of type 1, 2, 4, and 5, output the result on a separate line.

sample

5 5
1 2 3 4 5
1 1 5 3
2 1 5 3
4 1 5 3
5 1 5 3
3 3 10

3
3
2
4