String Palindrome Queries

You are given a string $S = s_1 s_2 \dots s_n$ of length $n$. For $x \le y$, $S_{x,y}$ is the substring $s_x \dots s_y$; for $x > y$, $S_{x,y}$ is the empty string.

Process $m$ queries in the order they are given. There are two kinds.

Question query. You are given integers $i$ and $j$. Decide whether the substring $S_{i,j}$ is a palindrome.

Modification query. One of the following three.

1. You are given integers $i$, $j$, $k$. Cut $S$ into three parts $S_{1,i-1}$, $S_{i,j}$, $S_{j+1,n}$, any of which can be empty. Concatenate the first part with the last one into $T = S_{1,i-1} S_{j+1,n}$, whose length is $n' = n - (j - i + 1)$. Insert the middle part after the $k$-th character of $T$, forming $S' = T_{1,k} S_{i,j} T_{k+1,n'}$, and set $S$ to $S'$.
2. You are given integers $i$ and $j$. Reverse the substring $S_{i,j}$.
3. You are given an integer $i$ and a character $c$. Insert $c$ right before position $i$, that is, set $S = S_{1,i-1} c S_{i,n}$.

The third modification query makes the string one character longer, so $n$ means the length of the string just before the current query is processed.

Write a program that runs the queries above.

The first line contains two space-separated integers $n$ and $m$. ($1 \le n \le 10^5$, $1 \le m \le 10^5$)

The second line contains the $n$ characters of the initial string.

Each of the next $m$ lines contains one query.

• A question query has the form Q i j. ($1 \le i \le j \le n$)
• Modification query 1 has the form M 1 i j k. ($1 \le i \le j \le n$, $0 \le k \le n - (j - i + 1)$)
• Modification query 2 has the form M 2 i j. ($1 \le i \le j \le n$)
• Modification query 3 has the form M 3 i c, where $c$ is a single character. ($1 \le i \le n + 1$)

On every line, $n$ is the length of the string just before that query is processed. You can assume that the string contains only lowercase letters of the English alphabet at all times. You may assume that the input is valid.

For each question query, print the answer on its own line. Print YES if $S_{i,j}$ is a palindrome and NO otherwise. Do not print the quotes.

In the first example the modification queries change the string like this.

• Start: $S =$ banana
• After M 2 2 3: $S =$ bnaana
• After M 2 5 6: $S =$ bnaaan
• After M 3 7 b: $S =$ bnaaanb
• After M 1 1 2 4: $S =$ aaanbnb

The last modification query cuts out the block bn and puts it back after the first four characters of the remaining string aaanb.