Problem A
Unreliable Messengers
---- 2003年 会津大会 ----

The King of a little Kingdom on a little island in the Pacific Ocean frequently has childish ideas. One day he said, “You shall make use of a message relaying game when you inform me of something.” In response to the King’s statement, six servants were selected as messengers whose names were Mr. J, Miss C, Mr. E, Mr. A, Dr. P, and Mr. M. They had to relay a message to the next messenger until the message got to the King.
 「島に住む国王が面白いことを言った、「何かを伝えたい時に、メッセージのリレーゲームでないといかん。」それで、Jさん、Cさん、Eさん、Aさん、Pさん、Mさんら6人が選ばれ、国王にメッセージが伝わるまで、互いにメッセージのリレーをしないといけなくなった。」

Messages addressed to the King consist of digits (‘0’-‘9’) and alphabet characters (‘a’-‘z’, ‘A’-‘Z’). Capital and small letters are distinguished in messages. For example, “ke3E9Aa” is a message.
 「国王に届くメッセージは数字と英字で書かれる。大文字小文字は区別される。例えば、“ke3E9Aa” は1通のメッセージ。」

Contrary to King’s expectations, he always received wrong messages, because each messenger changed messages a bit before passing them to the next messenger. Since it irritated the King, he told you who are the Minister of the Science and Technology Agency of the Kingdom, “We don’t want such a wrong message any more. You shall develop software to correct it!” In response to the King’s new statement, you analyzed the messengers’ mistakes with all technologies in the Kingdom, and acquired the following features of mistakes of each messenger. A surprising point was that each messenger made the same mistake whenever relaying a message. The following facts were observed.
 「期待に反して、国王にいつも間違ったメッセージしか伝わらなかった。怒った国王は科学技術大臣に命令した。「うんざりだ。エラーを直せ!」大臣が頑張った結果、以下の特徴を見つけ出した。また、すべてのメッセージに同じ間違いがあったことも突き止めた。」

Mr. J rotates all characters of the message to the left by one. For example, he transforms “aB23d” to “B23da”.
 「Jさんはメッセージを一文字左に回転させる。例、“aB23d”→“B23da”。」

Miss C rotates all characters of the message to the right by one. For example, she transforms “aB23d” to “daB23”.
 「Cさんはメッセージを一文字右に回転させる。例、“aB23d”→“daB23”。」

Mr. E swaps the left half of the message with the right half. If the message has an odd number of characters, the middle one does not move. For example, he transforms “e3ac” to “ace3”, and “aB23d” to “3d2aB”.
 「Eさんはメッセージの左半分と右半分とを入れ替える。メッセージの文字数が奇数の場合、真ん中の文字はそのまま。例、“e3ac”→“ace3”、“aB23d”→“3d2aB”。」

Mr. A reverses the message. For example, he transforms “aB23d” to “d32Ba”.
 「Aさんはメッセージを左右逆にする。例、“aB23d”→“d32Ba”。」

Dr. P increments by one all the digits in the message. If a digit is ‘9’, it becomes ‘0’. The alphabet characters do not change. For example, he transforms “aB23d” to “aB34d”, and “e9ac” to “e0ac”.
 「Pさんはすべての数字の値を1つ増やす、つまり、数字が9なら、0になる。英字は変わらない。例、“aB23d”→“aB34d”、 “e9ac”→“e0ac”。」

Mr. M decrements by one all the digits in the message. If a digit is ‘0’, it becomes ‘9’. The alphabet characters do not change. For example, he transforms “aB23d” to “aB12d”, and “e0ac” to “e9ac”.
 「Mさんはすべての数字の値を1つ減らす、つまり、数字が0なら、9になる。英字は変わらない。例、“aB23d”→“aB12d”、 “e0ac”→“e9ac”。」

The software you must develop is to infer the original message from the final message, given the order of the messengers. For example, if the order of the messengers is A→J→M→P and the message given to the King is “aB23d”, what is the original message? According to the features of the messengers’ mistakes, the sequence leading to the final message is

    “32Bad”→ A →“daB23”→ J →“aB23d”→ M →“aB12d”→ P →“aB23d”:

As a result, the original message should be “32Bad”.
 「6人のリレー順番が判ったとして、最後のメッセージを元に戻さないといけない。例えば、リレーの順番がA→J→M→Pの元で、国王に伝わったメッセージが “aB23d” だとすると、元のメッセージ “32Bad” に戻さないといけない。」

Input

The input format is as follows.
 「入力フォーマットは以下の通り。」

   n
   The order of messengers
   The message given to the King
   ...
   The order of messengers
   The message given to the King

The first line of the input contains a positive integer n, which denotes the number of data sets. Each data set is a pair of the order of messengers and the message given to the King. The number of messengers relaying a message is between 1 and 6 inclusive. The same person may not appear more than once in the order of messengers. The length of a message is between 1 and 25 inclusive.
 「最初の行に正の整数nが入り、データセットの数を表す。各データセットは、リレーの順番と国王に伝わったメッセージとのペアだ。リレーに参加する人数は1から6まで。1人が2度以上リレーすることはない。メッセージの長さが1から25まで。」

Output

The inferred messages are printed each on a separate line.
 「各行に元のメッセージを表示すること。」

Sample Input

5
AJMP
aB23d
E
86AE
AM
6
JPEM
WaEaETC302Q
CP
rTurnAGundam1isdefferentf

Output for the Sample Input

32Bad
AE86
7
EC302QTWaEa
TurnAGundam0isdefferentfr

Comments are closed.

Post Navigation