Enigma

During the Second World War the German military relied on one special machine to secure its communications: the Enigma (see Figure 4). Breaking the Enigma cipher was one of the great successes of Allied cryptanalysis, a triumph usually credited to the rise of digital computation and to the brilliant people gathered at Bletchley Park, England's secret codebreaking headquarters. The reason is simple: although Enigma is certainly secure against pen-and-paper attacks, it is fairly easy to break with a digital computer.

Figure 4: An Enigma machine.

Enigma is a rotor machine, a cipher design popular at the time. A rotor is an insulated disk with electrical contacts spaced uniformly around both faces, one contact per letter of the alphabet. Inside the disk, conducting paths connect the contacts in pairs, one contact on each face. A current entering one face travels along an internal path and emerges at some contact on the other face (Figure 5 shows a 3D view of two rotors). Figure 6 is a schematic side view of the whole rotor system: Enigma has three rotors $\pi_0$, $\pi_1$, $\pi_2$ plus one additional reflecting rotor $\pi_R$.

Figure 5: 3D view of two rotors.

Figure 6: Side view of the Enigma rotor system.

The input to Enigma is a stream of letters with no spaces. Each character passes through the following steps in order:

1. The plaintext letter is permuted by an initial permutation $IP$, implemented by a plugboard.
2. The character from step 1 passes through the three rotors $\pi_0$, $\pi_1$, $\pi_2$ in turn.
3. The resulting character passes through the reflecting rotor $\pi_R$.
4. The character from step 3 passes back through the rotors $\pi_2$, $\pi_1$, $\pi_0$ (i.e., in the opposite direction).
5. The character from step 4 is permuted by the inverse $IP^-1$ of the initial permutation.

The clever part of using rotors is that after each character is processed, and before the next one, the rotors may turn by some amount (i.e., by some number of letters). In Enigma, $\pi_0$ turns one position anti-clockwise for every character. When $\pi_0$ completes a full round (i.e., after 26 characters) $\pi_1$ advances by one position. Likewise, $\pi_2$ advances by one when $\pi_1$ completes a full revolution, and the reflecting rotor $\pi_R$ advances when $\pi_2$ completes its revolution. So $\pi_R$ is the slowest of the four rotors.

The same process serves for both encryption and decryption, provided the permutation $\pi_R$ realized by the reflecting rotor is an involution. That means $\pi_R = \pi_R^-1$, or equivalently $\xi = \pi_R(\zeta)$ whenever $\zeta = \pi_R(\xi)$. You may assume this condition holds.

The secret key of Enigma consists of (1) the rotors $\pi_0$, $\pi_1$, $\pi_2$, $\pi_R$, (2) the plugboard permutation $IP$, and (3) the initial rotational displacements $k_0$, $k_1$, $k_2$, $k_R$ of $\pi_0$, $\pi_1$, $\pi_2$, $\pi_R$ (described below).

You have been time-warped to Bletchley Park together with your laptop, and you must help decipher some messages intercepted during the day. You are given the entire ciphertext, part of the plaintext, and part of the Enigma key. Determine the correct key and complete the plaintext by decoding the ciphertext.

The first line contains the number of scenarios.

Each scenario begins with the secret key, given on 6 lines. The first four lines specify the rotors $\pi_0$, $\pi_1$, $\pi_2$, $\pi_R$, each as a sequence of 26 lowercase letters. Character $i$ (for $1 \le i \le 26$) gives the image of the $i$-th letter of the alphabet (for example, "bha..." means "a" maps to "b", "b" maps to "h", "c" maps to "a", and so on). Physically the sequence is listed in clockwise direction as seen from the front of the rotor stack $\pi_0, \dots, \pi_R$.

The fifth line gives the plugboard permutation $IP$ in the same format. The sixth line gives the initial displacements $k_0$, $k_1$, $k_2$, $k_R$ of the four rotors $\pi_0$, $\pi_1$, $\pi_2$, $\pi_R$ as a string of four letters, where "a" means the rotor is in its original position (as defined by the rotor specification above), "b" means it is rotated by one position in the usual direction, and so on. For example, "dgaa" means $\pi_0$ starts with displacement 3, $\pi_1$ with 6, and $\pi_2$, $\pi_R$ both in their original position.

After the key come two lines, each containing between 1 and 80 lowercase letters and nothing else. The first line is the plaintext; the second line is the ciphertext.

The plaintext and any part of the key may be incomplete, i.e., some positions in the strings may be a question mark "?". The number of question marks in one scenario's input is at most 3.

For each scenario, first print a line "Scenario #i:", where i is the scenario number starting at 1. On the next line print the completed, decrypted plaintext. You may assume a solution exists and is unique. Terminate each scenario's output with a blank line.