描述

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

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

格式

输入格式

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

输出格式

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

样例1

样例输入1

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

样例输出1

4
1

限制

每个测试点4s。

提示

来源

NOI 2007 Day 1