Emma planned to buy a string $S$ consisting of lowercase English characters of size $N$ as a gift for her friend Ava on her birthday. Ava had $Q$ other friends who also wanted to contribute but were not happy with the string. So all $Q$ of her friends decide to do either of the two operations :

• $1$ $x$ - Give an index $x$ and ask Emma to reverse the string from index $x$ to $N-x-1$.
• $2$ $x$ - Give an index $x$ and ask Emma to change the character at index $x$ to the alphabetically next character. For example, if the character was $a$, it would become $b$ (assume that $a$ is alphabetically next to $z$).

All of this was too much for Emma to handle alone. So she asked you to help her find the final string after doing all the operations.

Note : Assume 0-based indexing.

Input Format:

• The first line of input contains an integer $T$, denoting the number of test cases.
• The first line of each test case contains two integers, $N$ and $Q$, denoting the size of the string and the number of friends of Ava respectively.
• The following line contains a string of size $N$.
• The next $Q$ line contains two integers and is one of two types :
  •  $1$ $x$ - denoting that Emma needs to reverse the string from index $x$ to $N - x - 1$ (it is guaranteed that $x$ will be less than $N - x - 1$).
  •  $2$ $x$ - denoting that Emma needs to change the $x$'th character to alphabetically next character.

Output Format:
For each test case, print a string of size $N$ denoting the final string.

Constraints:
$1 \leq T \leq 5$
$1 \leq N, Q \leq 10^5$
$S$ contains all lower case English alphabets.
$0 \leq X < N$