Dynamic K-th Order Statistics Query

Given a sequence of n integers \(a_1, a_2, \dots, a_n\), you are required to support two types of operations:

• Q l r k: Query the \(k\)-th smallest number in the subarray \([l, r]\).
• C x y: Change the value at index \(x\) to \(y\).

Note that the indices are 1-indexed.

inputFormat

The first line contains two integers n and q: the number of elements in the sequence and the number of operations, respectively.

The second line contains n space-separated integers representing the sequence.

Each of the next q lines represents an operation in one of the following formats:

• Q l r k
• C x y

outputFormat

For each query operation (Q), output the \(k\)-th smallest number in the specified subarray on a new line.

sample

5 5
1 5 2 6 3
Q 2 5 3
C 3 4
Q 2 5 3
C 1 7
Q 1 3 2

5
5
5