#2556. 动态区间第 k 小

动态区间第 k 小

Description

NN 个数a[1],a[2],,a[N]a [1], a [2], …, a [N ], 求解a[i],a[i+1],,a[j]a [i ], a [i +1], …, a [j ]kk 小的数是多少ij0<kj+1i(i ≤j ,0<k ≤j +1-i )

有两种操作指令:

QQ ii jj kk 表示查询a[i],[i+1],,a[j]a [i ], [i +1], …, a [j ]的第kk 小的数;

CC ii tt 表示将a[i]a [i ]修改为tt

Format

Input

11行包含一个整数T0<T4T (0<T ≤4),表示测试用例数。每 个测试用例的第1行都包含两个整数N1N5×104N (1≤N ≤5×10^4 )M1M104M (1≤M ≤10^4 ),表示NN 个数和MM 行指令。后面一行包含NN 个数,第ii 个数表 示a[i]a [i ]。接下来的MM 行,每行都包含一个指令。保证在任何时候,a[i]a [i ]都是小于10910^9 的非负整数。

Output

对每个查询操作,都单行输出答案。

Samples

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
3
6
3
6

来源

ZOJ2112