Before you start solving this one. Let's have some fun with Mr President. Click here : http://trumpdonald.org/
Now let's get back to our CSE society. :P
Mr Paaltu has a string A containing lowercase english alphabets. He performed Q steps on it. In each step he chooses two integers L and R and performs cyclic shift on each character of A from position L to R (inclusive). Cyclic shift means alphabets are shifted to the next alphabet as per the english dictionary. i.e., a shifted to b, z shifted to a, y shifted to z.
See sample example for more clarification.
After doing all the q steps a new string B is produced.
Now after few days Mr Assi - The GS Buoy decided to restore back the original string A from B using information of all the steps performed by Mr Paaltu. Help Mr Assi to restore it.
The first line of the input contains a single integer T (1 ≤ T≤ 100) — the number of test cases.
For each test case,
First line contains integer N and Q ( 1 <= Q <= 10^4 ), here q is no of queries .
Second line contains a string B of lowercase English alphabets of length N+1 ( 1<=N <= 2*10^4).
Then Q lines follows, each line contains two integer L and R ( 1 <= L <= R <= N ).
Print T lines. In each line print restored string A.
AUTHOR : spaul100
Here, B = ceggb
Let's try to form B from A.
Let A be abcdz
After Step 1 : (1,3) : bcddz
After Step 2 : (2,4) : bdeez
After Step 3 : (1,5) : ceffa
After Step 4 : (3,3) : cegfa
After Step 5 : (4,5) : ceggb
So, abcdz is a valid answer.