[NOI2007]项链工厂

T 公司是一家专门生产彩色珠子项链的公司。最近，T 公司计划推出一套项链自助生产系统，使顾客能够自行设计项链。该系统的硬件部分已经完成，现在需要编写软件来模拟其操作。

一条项链由 $N$ 颗珠子组成，每颗珠子的颜色是 $1,2,\ldots,c$ 中的一种。项链被固定在一个平板上，平板上的某个位置被标记为位置 $1$，沿顺时针方向，其余位置依次编号为 $2,3,\ldots,N$。

软件系统需要支持以下命令：

• R k（Rotate）：将整条项链上的珠子顺时针旋转 $k$ 个位置。位置的编号保持不变。
• F（Flip）：以穿过位置 $1$ 和圆心的固定对称轴翻转项链。位置 $1$ 上的珠子保持不动，其余珠子按环形编号互换。等价地，原位置 $p$ 上的珠子移动到位置 $2-p\pmod N$，并将结果归一化到 $1$ 至 $N$。
• S i j（Swap）：交换位置 $i$ 与位置 $j$ 上的珠子。
• P i j x（Paint）：将从位置 $i$ 开始，沿顺时针方向到位置 $j$ 为止的所有珠子染成颜色 $x$，其中两端均包含在内。该区间可能跨过位置 $N$ 和位置 $1$。
• C（Count）：查询整条环形项链中颜色“部分”的数量。一个部分是环上颜色相同且连续的极大珠子集合。由于位置 $N$ 与位置 $1$ 相邻，如果两处珠子的颜色相同，它们属于同一个部分。
• CS i j（CountSegment）：将从位置 $i$ 开始，沿顺时针方向到位置 $j$ 为止的珠子视为一条线段，查询其中颜色相同且连续的极大段数量，两端均包含在内。即使查询恰好包含全部 $N$ 颗珠子，也仍按线段处理，线段的两个端点不会因为项链成环而合并。

注意，旋转操作移动的是珠子，而不会改变位置的编号；翻转操作始终以穿过位置 $1$ 和圆心的固定对称轴进行。

输入格式

第一行包含两个整数 $N,c$，分别表示项链中的珠子数量和颜色数量。

第二行包含 $N$ 个整数 $x_1,x_2,\ldots,x_N$，依次表示位置 $1$ 至位置 $N$ 上珠子的颜色。

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

接下来的 $Q$ 行，每行包含一条命令，格式为以下 $6$ 种之一：

• R k，其中 $1\le k\le N$；
• F；
• S i j，其中 $1\le i,j\le N$；
• P i j x，其中 $1\le i,j\le N$ 且 $1\le x\le c$；
• C；
• CS i j，其中 $1\le i,j\le N$。

输出格式

对于每条 C 或 CS 命令，输出一行一个整数，表示对应查询的答案。

样例输入

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

样例输出

4
1

数据范围

• $N\le 5\times 10^5$；
• $Q\le 5\times 10^5$；
• $c\le 10^3$；
• 对于所有初始颜色，$1\le x_i\le c$；
• 对于 R k 命令，$1\le k\le N$；
• 对于 S i j 和 CS i j 命令，$1\le i,j\le N$；
• 对于 P i j x 命令，$1\le i,j\le N$ 且 $1\le x\le c$。

来源与许可

本题为 NOI 2007 试题「项链工厂」，题面与测试数据整理自 BZOJ。

样例 1

输入

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

输出

4
1