Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 4039
Enigma Machine

Time Limit: 1 Second      Memory Limit: 65536 KB

Your friend has just sent you a piece of message encrypted by an Enigma Machine! As a programmer, you decided to decrypt the message yourself. You searched the Internet and found the following information:

Introduction to the Enigma Machine

The Enigma Machine consists of three main components: the plugboard, 3 rotors and the reflector.

Plugboard

You can regard the plugboard as a physical connection inside the machine. Suppose we have the plugboard setting "A-B, C-D", everytime we input A, we get B, and vice versa (input B, get A).

So under the "A-B, C-D" setting, if the input is a string "ABCDEFG", we'll get "BADCEFG".

Rotor

Every rotor has two attributes, the internal Ring Setting and the external Message Key. Both of them are a character in the English alphabet.

If a character is fed into a rotor, the following four steps will happen in order:

  1. Let A = 1, B = 2, ..., Z = 26. Calculate the difference between the Message Key and the Ring Setting. Let's assume $\Delta$ = MessageKey - RingSetting.

  2. Add $\Delta$ to the input character. If the character goes beyond Z, subtract 26 from it; If the character goes below A, add 26 to it so that it falls between A ~ Z. Let the resulting character of this step to be $c_2$.

  3. Look up $c_2$ in the "input" row of the corresponding rotor table. Read the character in the "output" row of the same column. Let this character be $c_3$.

  4. Subtract $\Delta$ from $c_3$ to get $c_4$. We adjust $c_4$ in the same way in step 2 to make $c_4$ falls between A ~ Z. $c_4$ is the output of the rotor.

Note that the above steps only applys when the character is inputted from the left. If the character is inputted from the right, we should look up $c_2$ in the "output" row of the rotor table, and get $c_3$ from the "input" row.

There are 5 types of rotors in total. Their rotor tables are shown below:

Rotor I
Input ABCDEFGHIJKLMNOPQRSTUVWXYZ
Output EKMFLGDQVZNTOWYHXUSPAIBRCJ
Rotor II
Input ABCDEFGHIJKLMNOPQRSTUVWXYZ
Output AJDKSIRUXBLHWTMCQGZNPYFVOE
Rotor III
Input ABCDEFGHIJKLMNOPQRSTUVWXYZ
Output BDFHJLCPRTXVZNYEIWGAKMUSQO
Rotor IV
Input ABCDEFGHIJKLMNOPQRSTUVWXYZ
Output ESOVPZJAYQUIRHXLNFTGKDCMWB
Rotor V
Input ABCDEFGHIJKLMNOPQRSTUVWXYZ
Output VZBRGITYUPSDNHLXAWMJQOFECK

For example, assume rotor I's Message Key is A, Ring Setting is B. We have $\Delta$ = A - B = -1. When character A is input from the left, it has to add delta first (becomes Z), look up the table (becomes J), subtract delta (becomes K). Thus the output is K.

Rotation of Rotor

Before processing a new character, the right-most rotor will rotate first, which means the Message Key will change to the next character in the alphabet (for example, from B to C, or from X to Y). Note that if the current Message Key is Z, it will change back to A. The Ring Setting is constant during the whole process.

But the rotate of the rotor is not this simple! When the rotor's Message Key reaches some specific character, it will make the next rotor (the rotor to its left) rotate as well!

  • For rotor I, this happens when its Message Key change from Q to R.

  • For rotor II, this happens when its Message Key change from E to F.

  • For rotor III, this happens when its Message Key change from V to W.

  • For rotor IV, this happens when its Message Key change from J to K.

  • For rotor V, this happens when its Message Key change from Z to A.

For instance, let's assume we have rotors III, II and I arranged from left to right, with the current Message Key of rotor I being Q and current Message Key of rotor II being A. Before processing a new character, the Message Key of rotor I will turn to R. Then it triggers rotor II to rotate, so the Message Key of rotor II changes from A to B.

Double Stepping

Another tricky point in the Enigma machine is the double stepping. It is a special mechnical structure in Enigma machine.

Double stepping only happens on the middle rotor. When the middle rotor is at its the "triggering" point, even if it is not triggered by the previous rotor (the rotor on its right), it will rotate itself, and then trigger the next rotor (the rotor on its left).

For instance, let's assume we have rotors III, II and I arranged from left to right, with the current Message Key of rotor III to be A, current Message Key of rotor II to be D, and current Message Key of rotor I to be Q.

Before processing a character, the right-most rotor (rotor I) rotates, so its Message Key becomes R. As "Q -> R" is the "triggering" point of rotor I, it triggers the rotation of rotor II as well, making the Message Key of rotor II to become E. The character is now processed.

Before processing the next character, the right-most rotor (rotor I) rotates, so its Message Key becomes S. But note that the middle rotor (rotor II) is at its "triggering" point! So rotor II also rotates, changing its Message Key from E to F, and triggers the rotation of rotor III, making its Message Key from A to B. The character is now processed.

Reflector

The reflector is simple. It just maps the character from the first row of the following table to the second row:

Input ABCDEFGHIJKLMNOPQRSTUVWXYZ
Output YRUHQSLDPXNGOKMIEBFZCWVJAT
Decryption Procedure

The decryption of the message is done one character at the time. To decrypt a character $c$, do the following steps:

  1. Rotate the rotors according to the rule.

  2. Input $c$ to the plugboard, and get the output $c_2$.

  3. Input $c_2$ from the left of the left-most rotor, and get the output $c_3$.

  4. Input $c_3$ from the left of the middle rotor, and get the output $c_4$.

  5. Input $c_4$ from the left of the right-most rotor, and get the output $c_5$.

  6. Input $c_5$ to the reflector, and get the output $c_6$.

  7. Input $c_6$ from the right of the right-most rotor, and get the output $c_7$.

  8. Input $c_7$ from the right of the middle rotor, and get the output $c_8$.

  9. Input $c_8$ from the right of the left-most rotor, and get the output $c_9$.

  10. Input $c_9$ to the plugboard, and get the output $c'$.

  11. $c'$ is the decrypted character.

After reading the above information, you decided to write a program to imitate the decryption process of the Enigma Machine.

Input

There are multiple test cases. The first line of the input contains an integer $T$ (about 100), indicating the number of test cases. For each test case:

The first line is a string $s$ ($|s| \le 1000$) consisting of uppercase English characters, indicating the message you need to decrypt.

The second line is a permutation of the uppercase English characters ABC...Z, indicating the setting of the plugboard. The $i$-th character $c_i$ means that if you input the $i$-th character in the alphabet, you will get $c_i$ as the output. It's guaranteed that the setting is legal.

The third line contains three integers (not seperated by a space) ranging from 1 to 5, indicating the type of three rotors from left to right.

The fourth line contains two strings $r$ and $m$ both of length 3, where $r$ indicates the Ring Settings of the rotors, and $m$ indicates the initial Message Keys of the rotors.

Output

For each test case output one line, the decrypted message.

Sample Input

3
JLEERJGZFBUMQL
BADCEFGHIJKLMNOPQRSTUVWXYZ
321
BAD ZDO
WERFNSDDMUJASYZWQT
VTLDKFYHPJECONMIQRSBUAWXGZ
514
ZLR SLJ
WKODEZOQJORBSGBATETZGWVJYVPSUMREBWLZIWJRLMJVJHQNTTBUNEFPIJMLYBXBPFYSUDDRLSIQAIXKATFKZGUKSLAERH
VTLDKFYHPJECONMIQRSBUAWXGZ
233
ZOJ JUN

Sample Output

ZOJMONTHLYJUNE
GOODLUCKANDHAVEFUN
THISISAVERYVERYLOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOONGMESSAGE

Author: FAN, Haoran; WENG, Caizhi
Source: ZOJ Monthly, June 2018
Submit    Status