빨래줄

시간 제한2초메모리 제한1024 MB

요약

세 가지 색 셔츠가 놓인 줄에서 구간별 색 개수를 세고, 구간을 잘라 앞이나 뒤로 옮기거나 뒤집는 연산을 처리합니다.

문제

주크는 프로그래밍 대회에서 받은 빨간색, 초록색, 파란색 셔츠를 많이 모았다. 그는 셔츠를 빨아서 순서대로 빨랫줄에 널었다. 그런데 빨랫줄 위 셔츠의 배열이 마음에 들지 않았다.

그래서 주크는 가장 보기 좋은 셔츠 배열과, 그 배열을 만드는 데 필요한 셔츠 이동 방법을 계산했다. 다만 이동하는 중간에도 셔츠가 모두 남아 있는지 확인하고 싶어 한다. 그래서 빨랫줄의 특정 구간에 특정 색 셔츠가 몇 장 있는지 알고 싶어 한다.

첫 줄에 셔츠 수 $N$ 과 질의 수 $Q$ 가 주어진다 ( $1 \le N \le 10^5$ , $1 \le Q \le 10^5$ ).

둘째 줄에는 길이 $N$ 의 문자열이 주어진다. 이 문자열은 셔츠의 초기 순서이며, P는 빨간색, R은 초록색, S는 파란색 셔츠를 뜻한다.

다음 $Q$ 개의 줄에는 T $L$ $R$ 형태의 질의가 한 줄에 하나씩 주어진다 ( $1 \le L \le R \le N$ ). $T$ 는 질의 종류이고, $L$ 과 $R$ 은 질의가 적용되는 셔츠의 위치이다. 질의는 다음 여섯 가지 중 하나이다.

$T$ 가 PUNASEID이면, 빨랫줄의 $L$ 번째부터 $R$ 번째까지 구간에 있는 빨간색 셔츠 수를 구한다.
$T$ 가 ROHELISI이면, 같은 구간에 있는 초록색 셔츠 수를 구한다.
$T$ 가 SINISEID이면, 같은 구간에 있는 파란색 셔츠 수를 구한다.
$T$ 가 ETTE이면, $L$ 번째부터 $R$ 번째까지 구간을 잘라 빨랫줄의 맨 앞에 묶는다. 구간을 떼어낸 뒤 생긴 두 끝은 서로 묶어서 셔츠가 떨어지지 않게 한다.
$T$ 가 TAHA이면, $L$ 번째부터 $R$ 번째까지 구간을 잘라 빨랫줄의 맨 뒤에 묶는다. 구간을 떼어낸 뒤 생긴 두 끝은 서로 묶어서 셔츠가 떨어지지 않게 한다.
$T$ 가 POORA이면, $L$ 번째부터 $R$ 번째까지 구간을 잘라 뒤집은 뒤 원래 자리에 다시 묶는다.

PUNASEID, ROHELISI, SINISEID 질의마다 답을 한 줄에 하나씩 출력한다. 각 답은 한 개의 정수이다.

예제 1

입력

5 6
PPSRR
POORA 1 3
PUNASEID 1 1
ETTE 4 5
ROHELISI 1 2
TAHA 1 2
SINISEID 1 1

예상 출력

0
2
1