목걸이 공장

회사 T는 색이 있는 구슬로 목걸이를 판매한다. 이 목걸이는 디자인이 트렌디하고 스타일이 다양하며 가격도 저렴해서 젊은 층에게 인기가 많다. 회사 T는 고객이 가장 아름답다고 생각하는 목걸이 디자인을 직접 고를 수 있도록 목걸이 '뷔페' 생산 시스템을 도입하기로 했다.

목걸이 뷔페 생산 시스템은 하드웨어와 소프트웨어로 구성된다. 소프트웨어는 사용자와 상호작용하며 하드웨어를 제어하고, 하드웨어는 소프트웨어가 보낸 명령을 받아 지정된 목걸이를 만든다. 하드웨어는 이미 완성되었지만 소프트웨어는 아직 개발되지 않았다. 회사 T는 전국 정보올림피아드에 출전한 당신에게 소프트웨어 시뮬레이션 시스템 작성을 맡겼다.

목걸이에는 구슬 $N$개가 있고, 각 구슬의 색은 1, 2, ..., $c$ 중 하나이다. 목걸이는 평평한 판 위에 고정되어 있다. 판 위의 한 지점을 위치 1로 정하고, 거기서 시계 방향으로 나머지 지점을 위치 2, 3, ..., $N$이라고 한다.

프로그램은 아래 명령을 지원해야 한다.

첫 줄에 구슬의 개수 $N$과 색의 개수 $c$가 주어진다.

둘째 줄에는 위치 1부터 위치 $N$까지 구슬의 색 $x_1, x_2, \ldots, x_N$이 주어진다(1 ≤ $x_i$ ≤ $c$).

셋째 줄에는 질의의 개수 $Q$가 주어진다. 이어서 $Q$개의 줄에 위 형식 중 하나의 명령이 한 줄에 하나씩 주어진다.

C와 CS 명령마다 답을 한 줄에 정수 하나로 출력한다.

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

R 명령은 구슬을 회전시키는 것이지, 위치의 번호를 바꾸는 것이 아니다. F 명령의 대칭축은 항상 위치 1이다.

CS 명령은 세그먼트 안에 있는 구간의 수를 센다. 길이가 $N$인 세그먼트를 질의하는 경우에도 이를 세그먼트로 취급해야 한다.