Mathison has downloaded a modern text editor after he got bored with Vim. This editor, called PalEd, has some really nice functions implemented so Mathison decided to improve his programming skills by reverse engineering the editor.
The editor is a complex data structure that supports only lowercase letters and provides the following functions:
add x c: Character c is added after the position x.
get x: The character that lies on position x is returned.
rev x y: The substring that starts at x and ends at y is reversed.
eq x y len: The editor compares the substring that starts at x and
has a length of len to the substring that starts at y and has a length of len and returns "yes" if they are equal (and "no" otherwise)
pal x y: The editor checks if the substring that starts at x and ends at y is a palindrome and returns "yes" if it is and "no" otherwise.
Given an initial text of N characters and Q operations, your task is to implement the editor in order to help Mathison test his implementation of PalEd. Don't worry, the testing framework was already written by a friend of Mathison's!
The first line on the input file will contain the number of tests, T.
The description of a test begins with two space-separated integers, N and Q, representing the length of the initial string contained inside the editor, and the number of operations that are performed.
The next line contains N lowercase letters, representing the string inside the editor.
Each of the next Q lines contains one operation. All possible formats of an operation are presented in the statement above.
The output file will contain the answer, one per line, for each get, eq or pal operation.
| Input | Output |
|---|---|
2 8 8 mathison add 0 a pal 1 3 add 8 s rev 1 7 pal 7 9 get 3 rev 1 7 pal 7 9 11 8 abracadabra rev 1 3 pal 3 4 get 2 add 7 r eq 8 11 2 eq 3 11 2 rev 1 3 eq 3 11 2 | yes no h yes yes b yes no yes |
The editor after every operation (first test):
The editor after every operation (second test):