说明

一条项链包含 $N$ 个珠子，每个珠子的颜色是 $1,2,\cdots,c$ 中的一种。项链被固定在一个平板上，平板的某个位置被标记位置 $1$ ，按顺时针方向其他位置被记为 $2,3,\cdots,N$。

你将要编写的软件系统应支持如下命令：

输入格式

输入文件第一行包含两个整数 $N,c$，分别表示项链包含的珠子数目以及颜色数目。

第二行包含 $N$ 个整数，$x_1,x_2,\cdots,x_n$，表示从位置 $1$ 到位置 $N$ 的珠子的颜色，$1 \le x_i \le c$。

第三行包含一个整数 $Q$，表示命令数目。

接下来的 $Q$ 行每行一条命令，如上文所述。

输出格式

对于每一个 C 和 CS 命令，应输出一个整数代表相应的答案。

5 3
1 2 3 2 1
4
C
R 2
P 5 5 2
CS 4 1

4
1

提示

【数据规模和约定】

对于 $60\%$ 的数据，$N \le 1000$，$Q \le 1000$；

对于 $100\%$ 的数据，$N \le 5\times 10^5$，$Q \le 5\times 10^5$，$c \le 1000$。

关于旋转和翻转

注意旋转命令旋转“珠子”但不改变“位置”的编号，而反转命令始终以位置 $1$ 为对称轴。例如当 $N=10$ 时，项链上的位置编号如图 $1$：

但注意此时项链上的位置编号仍然如图 $1$ 所示，于是翻转的对称轴不变。因而再执行一次 F 命令时，项链的颜色如图 $4$ 所示。

关于 CountSegment 命令

CS 命令表示查询一个“线段”中有多少个“部分”。尤其注意当查询的长度等于 $N$ 时，我们仍然将查询部分作为“线段”理解。

例如在图 $4$ 所示的情况中，执行 CS 1 10 命令，查询从位置 $1$ 开始到位置 $10$ 结束的这个长度为 $10$ 的线段中有多少个“部分”，于是得到返回值 $3$。与之形成对照的是，若执行 C 命令，返回值则为 $2$。