String Palindrome Queries

Time limit2sMemory limit256 MB

Summary

Maintain a lowercase string under block moves, reversals, and single-character insertions, answering after each change whether a given substring reads the same forwards and backwards.

Level: Hard10 of 10
Topics: String, String matching, Implementation
Solved: No attempts yet

Problem

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.

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'$ .
You are given integers $i$ and $j$ . Reverse the substring $S_{i,j}$ .
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.

Input

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.

Output

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.

Hint

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.

Examples2

Example 1

Input

6 10
banana
Q 2 6
Q 2 5
M 2 2 3
Q 2 5
M 2 5 6
Q 1 6
M 3 7 b
Q 1 7
M 1 1 2 4
Q 4 7

Expected output

YES
NO
YES
NO
YES
NO

Example 2

Input

5 8
abcba
Q 1 5
M 1 1 1 4
Q 1 4
M 1 5 5 0
Q 1 5
M 3 1 x
Q 1 6
Q 2 6

Expected output

YES
NO
YES
NO
YES