8010 - 项链工厂

T 公司是一家专门生产彩色珠子项链的公司，其生产的项链设计新颖、款式多样、价格适中，广受青年人的喜爱。最近 T 公司打算推出一款项链自助生产系统，使用该系统顾客可以自行设计心目中的美丽项链。 该项链自助生产系统包括硬件系统与软件系统，软件系统与用户进行交互并控制硬件系统，硬件系统接受软件系统的命令生产指定的项链。该系统的硬件系统已经完成，而软件系统尚未开发， T 公司的人找到了正在参加全国信息学竞赛的你，你能帮助 T 公司编写一个软件模拟系统吗？
一条项链包含N个珠子，每个珠子的颜色是 1, 2, ... , c中的一种。项链被固定在一个平板上，平板的某个位置被标记位置1，按顺时针方向其他位置被记为2,3, ... ,N。

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

试题澄清:
关于旋转和翻转 注意旋转命令旋转“珠子”但不改变“位置”的编号，而反转命令始终以位置1为对称轴。
关于CountSegment命令CS命令表示查询一个“线段”中有多少个“部分”。尤其注意当查询的长度等于N时，我们仍然将查询部分作为“线段”理解。

输入第一行包含两个整数N, c，分别表示项链包含的珠子数目以及颜色数目。
第二行包含N个整数，x1, x2 ,..., xn，表示从位置1到位置N的珠子的颜色，1<= xi<=c 。
第三行包含一个整数Q，表示命令数目。接下来的Q行每行一条命令，如上文所述。

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

数据范围：
对于60%的数据，N <=1000 , Q <=1000；
对于100%的数据，N <=500000 , Q <=500000 , c <=1000。

NOI