Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 1036
Enigma 2

Time Limit: 10 Seconds      Memory Limit: 32768 KB

Background

During the Second World War, the German military forces mainly used one special machine to secure their communication: the Enigma (see Figure 4). Breaking the Enigma cipher is one of the main success stories of Allied cryptanalysis and the triumph was mainly attributed to the emergence of digital computation and the genius of the people working at Bletchley Park, the secret cryptanalysis headquarters in England. The reason for this is that, while Enigma is certainly secure against pen and paper attacks, it is quite easily breakable using digital computers.


Figure 4: An Enigma machine (picture source: http://www.nsa.gov/museum/enigma.html).

The Enigma was a rotor machine, a cipher method which was popular at that time. A rotor is an insulated disk on which electrical contacts, one for each letter of the alphabet, are placed uniformly around the periphery and on each side. An internal conduction path through the insulating material connects contacts in pairs, one on each side of the disk. An electric current entering on one side travels on an internal path through the rotor cross-section, emerging at one of the contacts on the other side (see Figure 5 for a 3D visualisation of two rotors). Figure 6 shows a schematic side view of the complete rotor system. It shows that the Enigma has three rotors 0, 2 plus an additional reflecting rotor R.


Figure 5: 3D view of two rotors.


Figure 6: Side view of the Enigma��s rotor system.

The input to Enigma is a stream of alphabetic characters without blanks. Every character is subject to the following steps:

1. The plaintext is subject to an initial permutation IP which is implemented by a plugboard.

2. The character resulting from step 1 is sent through the three rotors 0, 2.

3. The resulting character is then sent through the reflecting rotor R.

4. The character from step 3 is passed back through the rotors 2, 0 (i.e., in the opposite direction).

5. The character from step 4 is subject to the inverse IP-1 of the initial permutation IP.

The interesting point about the use of rotors is that after processing each character, every rotor might be rotated by a certain angle (i.e., a certain amount of letters) before processing the next character. With the Enigma, rotor 0 is rotated by one in anti-clockwise direction with every new character. When 0 has finished one round (i.e., after processing 26 characters), rotor 1 moves by one character. Similarly, rotor 2 is rotated by one character when 1 has finished one revolution, and the reflecting rotor R moves when 2 has finished its rotation. Obviously, R is the slowest of the four rotors.

The process described above can be used both for encryption and decryption, provided that the permutation R implemented by the reflecting rotor is an involution. That means R = R-1, or, equivalently, whenever . You may assume that this condition holds.

The secret key of the Enigma consists of (1) the rotors 0, 2, and R, (2) the plugboard permutation IP, and (3) the initial rotational displacements k0, k1, k2, kR of 0, 2, and R (see below). The rotors were changed infrequently and were selected from a set of four possible rotors in the Wehrmacht model.


Problem

You are time-warped to Bletchley Park together with your laptop and should help to decipher some messages which have been intercepted over the day. You are given the entire ciphertext, parts of the plaintext, and parts of the Enigma key. Your task is to determine the correct key and finally complete the plaintext by decoding the ciphertext.


Input

The first line contains the number of scenarios.

Each scenario begins with the secret key of the Enigma. The secret key is specified by 6 lines. The first four lines contain a specification of the rotors 0, 2 and R as a sequence of lowercase alphabetic characters. Character i (1<=i<=26) gives the mapping of the i-th character of the alphabet (e.g., "bha..." means that "a" is mapped to "b", "b" is mapped to "h", "c" is mapped to "a" etc.). Physically, the sequence of characters is given in clockwise direction looking from the front of the rotor stack 0, . . . , R. After the rotors follows a similar line giving the plugboard permutation IP. Finally, the sixth line of the key gives the initial displacement k0, k1, k2, kR of the four rotors 0, 2, and R as a string of four characters where "a" means that the rotor is in its original position (as defined by the rotor specification above), "b" means that it is rotated by one position in the usual way etc. For example, "dgaa" means that rotor 0 has initial displacement 3, 1 has 6, and 2, R are both in their original position.

After the key follow two lines, each containing at least 1 and at most 80 lowercase letters, and no other characters. The first line contains the plaintext while the second line contains the ciphertext. The plaintext and any part of the key may be incomplete, i.e., some positions in the strings may be question marks "?". The number of question marks in the input will be at most 3.


Output


The output for each scenario begins with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. In the next line you are to output the completed, decrypted plaintext. You can assume that a solution exists and that it is unique. Terminate the output for each scenario with a blank line.


Sample Input

2
wfbtiznuvcqejpokshxgmadyrl
hmrgnqpkjcaivwluebfzsyxtdo
druahlbfzvgmwckxpiqysontje
owtvskypjifmluahrqecndbzgx
?bcdefghijklmnopqrstuvwxyz
aaaa
manyorganizationsrelyoncom??ters
grsuztldsznkwnerdpfbovvqnobkyiqn
oqzunvhtxwryfebicmjpklsgda
zupogrskynxtwdfqvbliejcmha
kzvlyjuodmscewxtfbphriqgna
gbcnylaztwkfmdspqvoiurjxeh
rfyhkxbuvplgtqmdiewjosznca
dmeo
???
ave


Sample Output

Scenario #1:
manyorganizationsrelyoncomputers

Scenario #2:
acm


Source: Northwestern Europe 2001
Submit    Status