문자열 회문 질의

길이가 $n$인 문자열 $S = s_1 s_2 \dots s_n$이 있다. $x \le y$이면 $S_{x,y}$는 부분 문자열 $s_x \dots s_y$를 뜻하고, $x > y$이면 $S_{x,y}$는 빈 문자열이다.

이 문자열에 질의 $m$개를 주어진 순서대로 처리한다. 질의는 두 종류다.

질문 질의. 정수 $i$, $j$가 주어진다. 부분 문자열 $S_{i,j}$가 회문인지 판정한다.

변경 질의. 다음 세 가지 중 하나다.

1. 정수 $i$, $j$, $k$가 주어진다. $S$를 세 조각 $S_{1,i-1}$, $S_{i,j}$, $S_{j+1,n}$으로 자른다. 각 조각은 비어 있을 수 있다. 첫 조각과 마지막 조각을 이어 붙여 $T = S_{1,i-1} S_{j+1,n}$을 만들면 $T$의 길이는 $n' = n - (j - i + 1)$이다. 가운데 조각을 $T$의 앞에서 $k$번째 문자 뒤에 끼워 넣어 $S' = T_{1,k} S_{i,j} T_{k+1,n'}$을 만들고, $S$를 $S'$으로 바꾼다.
2. 정수 $i$, $j$가 주어진다. 부분 문자열 $S_{i,j}$를 뒤집는다.
3. 정수 $i$와 문자 $c$가 주어진다. 위치 $i$ 바로 앞에 $c$를 끼워 넣어 $S = S_{1,i-1} c S_{i,n}$으로 바꾼다.

세 번째 변경 질의는 문자열의 길이를 1 늘린다. 따라서 $n$은 각 질의를 처리하기 직전의 문자열 길이를 뜻한다.

위 질의를 순서대로 처리하는 프로그램을 작성하시오.

첫째 줄에 정수 $n$과 $m$이 공백으로 구분되어 주어진다. ($1 \le n \le 10^5$, $1 \le m \le 10^5$)

둘째 줄에 초기 문자열을 이루는 문자 $n$개가 주어진다.

다음 $m$개 줄에 질의가 한 줄에 하나씩 주어진다.

• 질문 질의는 Q i j 꼴이다. ($1 \le i \le j \le n$)
• 변경 질의 1은 M 1 i j k 꼴이다. ($1 \le i \le j \le n$, $0 \le k \le n - (j - i + 1)$)
• 변경 질의 2는 M 2 i j 꼴이다. ($1 \le i \le j \le n$)
• 변경 질의 3은 M 3 i c 꼴이고, $c$는 문자 하나다. ($1 \le i \le n + 1$)

각 줄의 $n$은 그 질의를 처리하기 직전의 문자열 길이다. 문자열은 어느 시점에나 영어 소문자로만 이루어진다고 가정해도 된다. 입력은 항상 유효하다고 가정해도 된다.

질문 질의마다 한 줄에 답을 출력한다. $S_{i,j}$가 회문이면 YES를, 아니면 NO를 출력한다. 따옴표는 출력하지 않는다.

첫 번째 예제에서 변경 질의가 문자열을 바꾸는 과정은 다음과 같다.

• 처음: $S =$ banana
• M 2 2 3 이후: $S =$ bnaana
• M 2 5 6 이후: $S =$ bnaaan
• M 3 7 b 이후: $S =$ bnaaanb
• M 1 1 2 4 이후: $S =$ aaanbnb

마지막 변경 질의는 블록 bn을 떼어내고, 남은 문자열 aaanb의 앞 네 글자 뒤에 그 블록을 끼워 넣는다.