Description

A necklace contains $N$ beads. Each bead’s color is one of $1, 2, \ldots, c$. The necklace is fixed on a flat board. Some point on the board is marked as position $1$, and in the clockwise direction the other positions are labelled $2, 3, \ldots, N$.

The software system you will write should support the following commands:

Input Format

The first line contains two integers $N, c$, representing the number of beads in the necklace and the number of colors, respectively.

The second line contains $N$ integers, $x_1, x_2, \cdots, x_N$, representing the colors of the beads from position $1$ to position $N$, where $1 \le x_i \le c$.

The third line contains an integer $Q$, representing the number of commands.

Each of the next $Q$ lines contains one command, as described above.

Output Format

For each C and CS command, output one integer representing the corresponding answer.

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

4
1

Hint

[Constraints and Conventions]

For 60% of the testdata, $N \le 1000$, $Q \le 1000$.

For 100% of the testdata, $N \le 500000$, $Q \le 500000$, $c \le 1000$.

About rotation and flip

Note that the rotation command rotates the beads but does not change the labels of the positions, and the flip command is always symmetric about position $1$. For example, when $N = 10$, the position labels on the necklace are as shown in Figure 1:

However, note that the position labels on the necklace still remain as shown in Figure 1, so the axis of symmetry for flipping does not change. Therefore, after executing another “F” command, the colors on the necklace are as shown in Figure 4.

About the CountSegment command

The CS command queries how many “segments” there are in a linear “segment” of the necklace. In particular, when the query length equals $N$, we still treat the query range as a linear “segment”.

For example, in the situation shown in Figure 4, executing the command CS 1 10 queries how many “segments” there are in the linear segment starting at position $1$ and ending at position $10$, which has length $10$, and the return value is $3$. In contrast, if you execute the C command, the return value would be $2$.

Translated by ChatGPT 5