T Corporation is a company which produces colorful necklaces. The necklaces designed by them are unique and fashionable, and because of the price, they are popular with the youth. Now, T Corporation intends to design a self-help Producing System.

This system includes hardware and software. The software is interactive and controls the hardware. Now the hardware has been completed, but the software is to develop. The workers find you, who is taking NOI. Could you please write a software system to simulate?

A necklace includes N beads. The color of each bead is one of 1..c. The necklace is fixed in a plain. One position of the plain is marked as Position 1, and the other positions are marked as 2..n in clockwise.
Your system should supply the orders as follow:

+------------+-------------------------------+--------------------------------------------------+
|Order       |Parameters restrictions        |Content                                           |
+------------+-------------------------------+--------------------------------------------------+
|R  k        |0 < k < N                      |It means Rotate K. Rotate the necklace by k       |
|            |                               |positions in clockwise. i.e. The bead in former 1 |
|            |                               |position will be transfer to position k+1, the    |
|            |                               |bead in former 2 position will be transfer to     |
|            |                               |position k+2, and so on.                          |
+------------+-------------------------------+--------------------------------------------------+
|F           |                               |It means Flip. Flip the plain by the given axis.  |
|            |                               |The bead in position 1 doesn't move.The bead in   |
|            |                               |position 2 will swap with the bead in position    |
|            |                               |N,the bead in position 3 will swap with the bead  |
|            |                               |in position n-1, and so on.                       |
+------------+-------------------------------+--------------------------------------------------+
|S i j       |1 <= i,j <= n                  |Swap the bead in position i and j.                |
+------------+-------------------------------+--------------------------------------------------+
|P i j x     |1 <= i,j <= n , x<= c          |It means Paint. Paint color x from position i to  |
|            |                               |position j in clockwise.                          |
+------------+-------------------------------+--------------------------------------------------+
|C           |                               |It means Count. Ask how many parts are there in   |
|            |                               |the necklace. We define some consecutive beads    |
|            |                               |in same color as a "part". Pay attention that C is|
|            |                               |different from CS 1,n.                            |
+------------+-------------------------------+--------------------------------------------------+
|CS i j      |1 <= i,j <= n                  |It means CountSegment i,j. Ask how many parts are |
|            |                               |there from position i to position j in clockwise, |
|            |                               |i and j included.                                 |
+------------+-------------------------------+--------------------------------------------------+

Input

The first line in input includes two integers N,C, representing the beads in the necklace and the number of colors. The second line contains N integers x1,x2...xn, representing the colors of beads from position 1 to position n,1<=xi<=c. The third line includes a integer q, as the number of orders. There is an order in the next q lines, as mentioned above.

For 60% test cases, n <= 1000, Q <= 1000;
For 100% test cases, n <= 500000, Q <= 500000.

Output

For every order starts with C and CS, print a integer as the answer.

Example

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

Output:
4
1

Test data is unofficial. If you have any questions, please contact me.