Mathison and the Palindromic Editor

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!

Constraints and notes

• 1 ≤ T ≤ 10
• 1 ≤ N, Q ≤ 100,000
• The editor and all operations are 1-based. For example, if we perform "add 1 x" on "abc" we get "axbc".
• yes/no must be printed in lowercase and without any quotes.
• A palindrome is a word, phrase, or sequence that reads the same backward as forward, e.g., madam or nurses run.
• Note: The problem may not be solvable in slower languages like Python or Java!
• Note: You may want to use faster reading methods!

Input

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.

Output

The output file will contain the answer, one per line, for each get, eq or pal operation.

Sample

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):

1. amathison
2. amathison
3. amathisosn
4. sihtamaosn
5. sihtamaosn
6. sihtamaosn
7. amathisosn
8. amathisosn

The editor after every operation (second test):

1. rbaacadabra
2. rbaacadabra
3. rbaacadabra
4. rbaacadrabra
5. rbaacadrabra
6. rbaacadrabra
7. abracadrabra
8. abracadrabra