[NOI2007] 项链工厂

T公司是一家专门生产彩色珠子项链的公司，其生产的项链设计新颖、款式多样、价格适中，广受青年人的喜爱。 最近T公司打算推出一款项链自助生产系统，使用该系统顾客可以自行设计心目中的美丽项链。该项链自助生产系 统包括硬件系统与软件系统，软件系统与用户进行交互并控制硬件系统，硬件系统接受软件系统的命令生产指定的 项链。该系统的硬件系统已经完成，而软件系统尚未开发，T公司的人找到了正在参加全国信息学竞赛的你，你能 帮助T公司编写一个软件模拟系统吗？

一条项链包含 $N$ 个珠子，每个珠子的颜色是 $1,2,…,c$ 中的一种。项链 被固定在一个平板上，平板的某个位置被标记位置 $1$ ，按顺时针方向其他位置被记为 $2,3,…,N$。  你将要编写的软件系统应支持如下命令：  

输入文件第一行包含两个整数 $N, c$，分别表示项链包含的珠子数目以及颜色数目。 第二行包含 $N$ 个整数，$x_1, x_2…, 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 500000$，$Q \le 500000$，$c \le 1000$。 关于旋转和翻转 注意旋转命令旋转“珠子”但不改变“位置”的编号，而反转命令始终以位置 1 为对称轴。例如当 N=10 时，项链上的位置编号如图1： 但注意此时项链上的位置编号仍然如图1所示，于是翻转的对称轴不变。因而再执行一次“F”命令时，项链的颜色如图4所示。   关于CountSegment命令 CS命令表示查询一个“线段”中有多少个“部分”。尤其注意当查询的长度等于 N 时，我们仍然将查询部分作为“线段”理解。 例如在图4所示的情况中，执行“CS 1 10”命令，查询从位置 1 开始到位置 10 结束的这个长度为 10 的线段中有多少个“部分”，于是得到返回值 3 。与之形成对照的是，若执行“C”命令，返回值则为 2