Necklace Factory

Time limit3sMemory limit256 MB

Summary

Simulate a necklace of N colored beads under rotate, flip, swap, and paint commands, and count the same-color runs in the whole necklace or in a segment.

Level: Hard8 of 10
Topics: Segment tree, Array, Implementation
Solved: No attempts yet

Problem

Company T sells necklaces with colored beads. The necklaces have fashionable designs, varied styles, and affordable prices, so they are popular with young people. Company T has decided to launch a necklace 'buffet' production system so that customers can choose which necklace design they find most beautiful.

The necklace buffet production system has a hardware system and a software system. The software system interacts with the user and controls the hardware system, and the hardware system receives commands from the software and produces the specified necklace. The hardware is already finished, but the software has not been developed yet. Company T asked you, a competitor at the National Olympiad in Informatics, to write a software simulation system.

A necklace has $N$ beads, and each bead has a color from 1, 2, ..., $c$ . The necklace is fixed to a flat board. One place on the board is position 1, and going clockwise from there, the other places are positions 2, 3, ..., $N$ .

Your program must support the following commands.

Command	Parameter constraints	Details
`R k`	0 < `k` < `N`	Rotate `k`. The necklace is rotated clockwise by `k` spots. The bead at position 1 moves to position `k` + 1, the bead at position 2 moves to position `k` + 2, and so on.
`F`		Flip. The necklace is flipped along its axis of symmetry. The bead at position 1 does not move, the bead at position 2 swaps with the bead at position `N`, the bead at position 3 swaps with the bead at position `N` - 1, and so on.
`S i j`	1 ≤ `i`, `j` ≤ `N`	Swap `i`, `j`. The bead at position `i` swaps places with the bead at position `j`.
`P i j x`	1 ≤ `i`, `j` ≤ `N`; `x` ≤ `c`	Paint `i`, `j`. The segment from position `i` to position `j`, both inclusive, is painted with color `x`.
`C`		Count. Find how many 'sections' the current necklace is made of. A section is a maximal run of consecutive beads that all have the same color.
`CS i j`	1 ≤ `i`, `j` ≤ `N`	CountSegment `i`, `j`. Find how many sections the segment from position `i` to position `j`, both inclusive, is made of in the current necklace.

Input

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

The second line contains $N$ integers $x_1, x_2, \ldots, x_N$ , the colors of the beads at positions 1 through $N$ , where 1 ≤ $x_i$ ≤ $c$ .

The third line contains an integer $Q$ , the number of queries. The next $Q$ lines each contain one command in one of the formats above.

Output

For each C and CS command, print the answer on its own line.

Constraints

$N \le 500000$ , $Q \le 500000$ , $c \le 1000$ .

Hints

The R command rotates the beads, not the position numbers. The F command always uses position 1 as its axis of symmetry.

The CS command counts sections inside a segment. Note that when the queried segment has length $N$ , it is still treated as a segment.

Examples1

Example 1

Input

Expected output

4
1