407417: GYM102787 B Pear TreaP

Have you ever heard of an eer-tree? It is a very special tree that does super cool stuff with palindromes. As you would expect of such a structure, the word eer-tree is a palindrome itself. Even cooler, if we do the same thing with a treap, we get a Pear Treap! What an epic palindrome!

What's that I hear? "Pear Treap isn't actually a palindrome," you say? Nonsense! I always write a and e together as one character, so it is totally a palindrome. Anyhow, here's your palindromic treap problem, as promised:

You have a string initially containing $$$n$$$ lowercase characters. Please perform the $$$q$$$ operations (that is, please solve each query before reading the next one) of the following types:

1. Delete all characters from position $$$l$$$ to position $$$r$$$ inclusive.

2. Insert the character $$$c$$$ at position $$$p$$$. After this query, the character at position $$$p$$$ will be $$$c$$$, and all characters initially with indecies $$$\geq p$$$ will be moved one space to the right.

3. Is the substring from position $$$l$$$ to position $$$r$$$ a palindrome? A substring from $$$l$$$ to $$$r$$$ is the continuous block of characters starting at position $$$l$$$, ending at position $$$r$$$.

The first line will contain two integers: $$$n$$$ and $$$q$$$. ($$$1 \leq n, q \leq 3*10^5$$$)

The second line will contain a string of $$$n$$$ lowercase letters. It will not contain the character that is $$$a$$$ and $$$e$$$ combined into one character.

The following $$$q$$$ lines each contain three integers, an are of one of the following forms:

- $$$1$$$ $$$l$$$ $$$r$$$. In this case $$$1 \leq l \leq r \leq currentStringLen$$$. This query will not appear if the string is empty.

- $$$2$$$ $$$c$$$ $$$p$$$. In this case $$$1 \leq p \leq currentStringLen+1$$$. $$$c$$$ is a lowercase character.

- $$$3$$$ $$$l$$$ $$$r$$$. In this case $$$1 \leq l \leq r \leq currentStringLen$$$. This query will not appear if the string is empty.

For each query of type 3, please print either "yes" or "no" depending on whether that substring is a palindrome or not.

4 4
aaaa
1 3 4
3 1 1
3 1 1
2 a 3

yes
yes

5 5
aaaaa
2 b 3
1 1 1
3 5 5
1 5 5
1 3 3

yes

For the full Pear Treap experience, you can pretend that I am forcing you to solve this problem ONLINE. There is no such requirement as this is just practice and that would make the statement more annoying, but it could easily show up in a real contest or as a subproblem.