Description

有由$N$ 个非负整数组成的序列：$a [1],a [2], …, a [N ]$，对该序列进行$M$ 个操作，操作形式：$①S X Y$，将$a [X ]$的值设置为$Y （a [X ]=Y ）$；$②Q L R D P$，求$[L , R ]$区间第$D$ 位是$P$ 的元素个数，$L$ 和$R$ 是序列的索引。注意：第$1$位是最低有效位。

Input

第$1$行包含一个整数$T$ ，表示测试用例的数量。每个测试用例的第$1$行都包含两个整数$N$ 和$M$ 。第$2$行包含$N$ 个整数：$a [1], a[2], …, a [N ]$。接下来的$M$ 行操作，若类型为$S$，则在该行中将包含两个整数$X、Y$ ；若类型为$Q$，则将包含$4$个整数$L、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。$

Output

对每个$Q$操作，都单行输出答案。

Samples

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