Problem A: スワップ暗号

R大学のとある2D好きな彼は、人に見られると赤面するような恥ずかしい文章を日頃からよく書いている。 そのため、第三者に自分の書いている文章を見られないために、彼が独自に考え出したスワップ暗号という手法により文章を暗号化している。 スワップ暗号では、次のようなステップをN回繰り返し、暗号化を行う。

1. 文字列のa_i番目とb_i番目を入れ替える
2. この2つの文字を、a_iとb_iの差分だけアルファベット順に戻す

ただし、アルファベット順で、'a'の前は'z'とする。

例えば、"aojwo"という文字列に対し、a₁=1、b₁=4、という暗号化操作を行ったとすると、次のようになる。

1. 1番目と4番目を入れ替える("aojwo"→"wojao")
2. この2つの文字'w'と'a'を、1と4の差分＝3だけアルファベット順に戻す("wojao"→"tojxo")
• 'w'は、アルファベット順に3戻すと、'w'→'v'→'u'→'t'となる
• 'a'は、アルファベット順に3戻すと、'a'→'z'→'y'→'x'となる

よって、"aojwo"は、"tojxo"と暗号化される。

この暗号化により彼の文章は、原文がわからないように暗号化できるはずだったのだが、あろうことか彼は暗号化に使用したスワップ操作の過程を流出させてしまった。 あなたの仕事は、暗号化された文字列と暗号化に使用したスワップ操作が与えられたとき"復号"を行うプログラムを作成し、2D好きな彼をはずかしめてやることである。

Input

入力は、複数のデータセットからなる。データセットの総数は20以下である。 各データセットは、次の形式をしている。

N
message
a1 b1
...
ai bi
...
aN bN

N(0 < N ≤ 100)は、暗号化するときにスワップ操作した回数を示す整数である。 messageは、暗号化されたデータを示す。 暗号データは、アルファベットの小文字のみで構成される文字列である。 messageの長さをlenとしたとき、2 ≤ len ≤ 100と仮定してよい。

a_i、b_iは、暗号化においてスワップを行った2つのインデックスを表している。 1 ≤ a_i < b_i ≤ lenと仮定してよい。 暗号化は、入力された順番にスワップ操作をしたものとする。

入力の終了は、0のみからなる1行で示される。このデータについては、処理する必要はない。

Output

各データセットに対して、復号した文字列を1行に出力せよ。

Sample Input

1
tojxo
1 4
5
uhcqmlmkv
4 5
6 9
3 6
1 7
3 6
5
shzxadexonr
8 9
3 9
5 8
4 9
10 11
0

Output for Sample Input

aojwo
shinryaku
shitadegeso

Note

Commentary

 

---