Comet OJ

C0325 [NOI2007Day2-A]项链工厂

内存限制：256 MB 时间限制：4000 ms

题目描述

T公司是一家专门生产彩色珠子项链的公司，其生产的项链设计新颖、款式多样、价格适中，广受青年人的喜爱。最近T公司打算推出一款项链自助生产系统，使用该系统顾客可以自行设计心目中的美丽项链。

该项链自助生产系统包括硬件系统与软件系统，软件系统与用户进行交互并控制硬件系统，硬件系统接受软件系统的命令生产指定的项链。该系统的硬件系统已经完成，而软件系统尚未开发，T公司的人找到了正在参加全国信息学竞赛的你，你能帮助T公司编写一个软件模拟系统吗?

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

屏幕快照 2019-06-10 下午1.47.29.png

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

屏幕快照 2019-06-10 下午1.48.12.png屏幕快照 2019-06-10 下午1.48.49.png

输入格式

第一行包含两个整数$N, c$，分别表示项链包含的珠子数目以及颜色数目。第二行包含$N$个整数，$x_1, x_2..., x_n$，表示从位置1到位置$N$的珠子的颜色，$1≤x_i≤c$。第三行包含一个整数$Q$，表示命令数目。接下来的$Q$行每行一条命令，如上文所述。

输出

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

样例

样例输入 1

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

样例输出 1

4
1

提示

【数据规模和约定】

对于60%的数据，$N≤1000，Q≤1000$;
对于100%的数据，$N≤500000，Q≤500000，c≤1000$。