A Special Text Editor

Time Limit: 4000/2000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Description

After AC all the hardest problems in the world , the ACboy 8006 now has nothing to do . So he develops a special text editor.The text editor is so special that it only supports 3 special operation: "Reverse","Shift" and "Query".

1.The "Reverse" command has 2 parameters A and B.
The format is "R A B". After the command executed, the editor will reverse the substring which is in the string from position A to position B.

2.The "Shift" command also has 2 parameters A and B.
The format is "S A B". After the command executed, the editor will translate every character in the substring which is in the string from positon A to position B to the NEXT character in alphabetic table.In another word, it will translate 'a' to 'b','b' to 'c' ... 'y' to 'z'. Specially it will translate 'z' to 'a'.

3.The "Query" command has only 1 parameter A.
The format is "Q A". When the text editor receives the command,it just reports the character which is in the postion A of the string now.


For example, let's consider the string "abcdefzh" whose length is 8.
After we operate the command "R 2 7", the string will be "azfedcbh".
Then after we operate the command "S 2 3", it will be "aagedcbh".

Now your task is to simulate the process, and output the exact character when you read a "Query" command. Is that easy ? Just come and AC it !

Input

The first line of the input contains an integer T which means the number of test cases. Then T test cases follow.
In the first line there are two integers N(0<N<=80000) and C(0<C<=3000) which indicate the length of the string and the number of the commands.
In the second line there is a string whose length is N and which is only consisted of lowercase letters.
Then C lines follow. Each line describes a command in the form of 'Q A' or 'R A B' or 'S A B' (0<A<=B<=N).

Output

For each "Query" command, output the character which the text editor reports.

Sample Input

1 8 5 abcdefzh Q 4 R 2 7 Q 3 S 2 3 Q 2

Sample Output

d f a

Hint

wangye

Source

2008杭电集训队选拔赛

提交代码