#2501. 序列操作

序列操作

说明

有由NN 个非负整数组成的序列:a[1],a[2],,a[N]a [1],a [2], …, a [N ],对该序列进行MM 个操作,操作形式:SXY①S X Y ,将a[X]a [X ]的值设置为Ya[X]=YY (a [X ]=Y )QLRDP②Q L R D P ,求[L,R][L , R ]区间第DD 位是PP 的元素个数,LLRR 是序列的索引。注意:第11位是最低有效位。

输入

11行包含一个整数TT ,表示测试用例的数量。每个测试用例的第11行都包含两个整数NNMM 。第22行包含NN 个整数:a[1],a[2],,a[N]a [1], a[2], …, a [N ]。接下来的MM 行操作,若类型为SS,则在该行中将包含两个整数XYX、Y ;若类型为QQ,则将包含44个整数LRDPL、R、D、P 。其中:$1≤T ≤50,1≤N , M ≤10^5 ,0≤a [i ]≤2^{31} -1,1≤X ≤N ,0≤Y≤2^{31} -1,1≤L ≤R ≤N ,1≤D ≤10,0≤P ≤9。$

输出

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

样例

1
5 7
10 11 12 13 14
Q 1 5 2 1
Q 1 5 1 0
Q 1 5 1 1
Q 1 5 3 0
Q 1 5 3 1
S 1 100
Q 1 5 3 1
1
1
5
0
1

来源

HDU5057