All Tracks Basic Programming Implementation Basics of Implementation Problem

Presidential Problem
Tag(s):

Very-Easy

Problem
Editorial
Analytics

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.

Input

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 Q ( 1 <= Q <= 10^4 ), no of queries .

Second line contains a string B of lowercase English alphabets of length N ( 1<=N <= 2*10^4).

Then Q lines follows, each line contains two integer L and R ( 1 <= L <= R <= N ).

Output

Print T lines. In each line print restored string A.

AUTHOR : spaul100

SAMPLE INPUT
1
5 5
ceggb
1 3
2 4
1 5
3 3
4 5
SAMPLE OUTPUT
abcdz
Explanation

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.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Notifications
View All Notifications