Description

对$N$个数$a [1], a [2], …, a [N ]$， 求解$a [i ], a [i +1], …, a [j ]$第$k$ 小的数是多少$（i ≤j ，0<k ≤j +1-i ）$？

有两种操作指令:

$Q$ $i$ $j$ $k$ 表示查询$a [i ], [i +1], …, a [j ]$的第$k$ 小的数；

$C$ $i$ $t$ 表示将$a [i ]$修改为$t$ 。

Format

Input

第$1$行包含一个整数$T （0<T ≤4）$，表示测试用例数。每 个测试用例的第1行都包含两个整数$N （1≤N ≤5×10^4 ）$和$M （1≤M ≤10^4 ）$，表示$N$ 个数和$M$ 行指令。后面一行包含$N$ 个数，第$i$ 个数表 示$a [i ]$。接下来的$M$ 行，每行都包含一个指令。保证在任何时候，$a [i ]$都是小于$10^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