Dynamic Range k-th Smallest Query with Updates and Insertions

In this problem, you are given a sequence of n fleas arranged in a row, each with its own jump strength a_i.

The flea king is enjoying the sight of the flourishing flea kingdom and decides to have some fun by querying the k-th smallest jump strength in a given interval. Specifically, each query is: "What is the k-th smallest value among the fleas from the x-th to the y-th (from left to right)?"

However, things change over time. Some fleas’ jump strengths are updated (they may increase or decrease), and sometimes a new flea is inserted at a specific position in the line. You need to process these operations online.

Operations:

• Q x y k: Query the k-th smallest number in the subarray from the x-th to y-th flea (1-indexed). It is guaranteed that the query parameters are valid.
• C x v: Update the jump strength of the flea at position x (1-indexed) to v.
• I x v: Insert a new flea with jump strength v at position x (1-indexed). After insertion, the new flea becomes the x-th element, and the rest are shifted to the right.

Note: All indices are 1-indexed. It is guaranteed that the operations are valid, and the queries will always ask for an existing k-th element.

The intended solution may use advanced data structures such as persistent segment trees or a combination of Fenwick trees and segment trees. However, for this problem, the input sizes are small enough so that a straightforward simulation with appropriate data structures will pass.

inputFormat

The first line contains two integers n and q (1 ≤ n, q ≤ 10⁵ in the worst-case, but in our test cases the sizes are small), representing the number of initial fleas and the number of operations.

The second line contains n integers a1, a2, ..., an representing the initial jump strengths.

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

• Q x y k — Query: output the k-th smallest element in the subarray from the x-th to y-th element.
• C x v — Change: update the element at position x to value v.
• I x v — Insert: insert a new element with value v at position x.

outputFormat

For each query operation (Q x y k), output a single line containing the answer.

sample

5 5
5 3 8 6 2
Q 1 5 3
C 3 1
Q 2 4 2
I 2 4
Q 1 3 1

5
3
3