Background

Company T specializes in producing necklaces made of colored beads. Its necklaces have fresh designs, diverse styles, and reasonable prices, and are popular among young people.

Recently, Company T plans to launch a self-service necklace production system. With this system, customers can design their own beautiful necklaces. The system consists of a hardware component and a software component. The software interacts with users and controls the hardware, and the hardware executes the software’s commands to produce the specified necklace. The hardware has already been completed, but the software has not yet been developed. The team at Company T has found you, a participant in a national informatics competition. Can you help Company T write software to simulate this system?

Problem 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