# Dynamic Rankings

Time Limit: 10 Seconds Memory Limit: 32768 KB

The Company Dynamic Rankings has developed a new kind of computer that is no
longer satisfied with the query like to simply find the k-th smallest number
of the given N numbers. They have developed a more powerful system such that
for N numbers a[1], a[2], ..., a[N], you can ask it like: what is the k-th smallest
number of a[i], a[i+1], ..., a[j]? (For some i<=j, 0

Your task is to write a program for this computer, which

- Reads N numbers from the input (1 <= N <= 50,000)

- Processes M instructions of the input (1 <= M <= 10,000). These instructions
include querying the k-th smallest number of a[i], a[i+1], ..., a[j] and change
some a[i] to t.

## Input

The first line of the input is a single number X (0 < X <= 4), the number
of the test cases of the input. Then X blocks each represent a single test case.

The first line of each block contains two integers N and M, representing N numbers
and M instruction. It is followed by N lines. The (i+1)-th line represents the
number a[i]. Then M lines that is in the following format

Q i j k or

C i t

It represents to query the k-th number of a[i], a[i+1], ..., a[j] and change
some a[i] to t, respectively. It is guaranteed that at any time of the operation.
Any number a[i] is a non-negative integer that is less than 1,000,000,000.

There're NO breakline between two continuous test cases.

## Output

For each querying operation, output one integer to represent the result. (i.e.
the k-th smallest number of a[i], a[i+1],..., a[j])

There're NO breakline between two continuous test cases.

## Sample Input

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

## Sample Output

3 6 3 6Submit

Source: Online Contest of Christopher's Adventure