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<k<=j+1-i that you have given to it). More powerful, you can even change the value of some a[i], and continue to query, all the same.

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
6

-----------------------------------------------------------------------------------------------------------------------------
題目意思是要對一個序列詢問某段當(dāng)中的第k大數(shù)，并且支持修改單個元素的操作。
50000的數(shù)據(jù)范圍顯然要我們用高級數(shù)據(jù)結(jié)構(gòu)來維護(hù)，但是很囧的問題就是：詢問區(qū)間要用線段樹，詢問第k大要用平衡樹。。。
解決這個問題的方法很簡單，就是線段樹套平衡樹，線段樹中的每個節(jié)點都有一棵平衡樹，維護(hù)線段樹所記錄的這個區(qū)間的元素。
這樣處理空間上是O(nlogn)的，因為線段樹有l(wèi)ogn層，每層的平衡樹所記的節(jié)點總數(shù)都有n個。
修改很容易想到，把所有包含要修改點的區(qū)間的平衡樹都修改了就行了，但查詢的時候又被囧到了：詢問的區(qū)間不一定就是線段樹里面某個節(jié)點記的某個區(qū)間。
。。最終還是去找了hyf神牛。。。他一語點破天機：二分答案。。
對于每次查詢，二分第k大的數(shù)是多少，在線段樹里查詢這個區(qū)間中小于等于這個值的有多少個，就可以得到答案了。
需要注意的細(xì)節(jié)是：對于一個數(shù)，可能會有重復(fù)，比如對于1 2 2 2 3，查詢第2大的數(shù)，當(dāng)而分到2的時候，可能查到的是第三個2，查詢結(jié)果也就是4。為了解決這個問題，可以在當(dāng)查詢不大于x的數(shù)的個數(shù)t1時，再查詢不大于x-1的數(shù)的個數(shù)t2，如果t2<k<=t1那么此時的x便是所求的第k大的數(shù)。
這樣的話，查詢是O(log(n)log(n)*log(MAXNUM))   (其實在查詢線段樹和平衡樹的時候不可能同時都達(dá)到log(n)，只是具體是多少我就算不來了。。望高手解答。。)，修改是O(log(n)*log(n))的(問題同上。。)，就可以在時間范圍內(nèi)解決了。