Necklace Factory
Company T specializes in producing colorful bead necklaces. Their necklaces feature innovative designs, diverse styles, and reasonable prices, making them popular among young people. Recently, Company T decided to launch a self-service necklace production system, allowing customers to design their own beautiful necklaces.
The self-service production system consists of a hardware system and a software system. The software system interacts with the user and controls the hardware system, which receives commands from the software to produce the specified necklace. The hardware system is already complete, but the software system has not yet been developed. Company T has found you, a participant in the National Olympiad in Informatics, and asks if you can help them write a software simulation system.
A necklace contains $N$ beads, and each bead has a color from $1, 2, \dots, c$. The necklace is fixed on a flat board. One position on the board is marked as position 1, and other positions are marked $2, 3, \dots, N$ in a clockwise direction.
The software system you are to write should support the following commands:
| Command | Parameter Constraints | Description |
|---|---|---|
R k |
$0 < k < N$ | Rotate $k$. Rotate the necklace on the board clockwise by $k$ positions. That is, the bead originally at position 1 moves to position $k+1$, the bead at position 2 moves to position $k+2$, and so on. |
F |
Flip. Flip the board along the given axis of symmetry. The bead originally at position 1 remains unchanged, the bead at position 2 is swapped with the bead at position $N$, the bead at position 3 is swapped with the bead at position $N-1$, and so on. | |
S i j |
$1 \le i, j \le N$ | Swap $i, j$. Swap the bead at position $i$ with the bead at position $j$. |
P i j x |
$1 \le i, j \le N, x \le c$ | Paint $i, j, x$. Paint the segment from position $i$ clockwise to position $j$ with color $x$. |
C |
Count. Query how many "segments" the current necklace consists of. A segment is defined as a contiguous sequence of beads of the same color. | |
CS i j |
$1 \le i, j \le N$ | CountSegment $i, j$. Query how many segments the segment from position $i$ clockwise to position $j$ consists of. |
Input
The first line of the input contains two integers $N$ and $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, \dots, 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 following $Q$ lines contains one command as described above.
Output
For each C and CS command, output an integer representing the corresponding answer.
Examples
Input 1
5 3 1 2 3 2 1 4 C R 2 P 5 5 2 CS 4 1
Output 1
4 1
Constraints
For 60% of the data, $N \le 1\,000$, $Q \le 1\,000$. For 100% of the data, $N \le 500\,000$, $Q \le 500\,000$, $c \le 1\,000$.
Subtasks
This problem has no partial points. Your program must produce output that matches the standard answer exactly to receive full marks; otherwise, you will receive no points.