G - Enigma

Podczas drugiej wojny światowej wojsko niemieckie używało przeważnie jednej maszyny do zabezpieczania komunikacji: Enigmy. Złamanie kodu Enigmy jest jednym z najważniejszych osiągnięć kryptoanalizy aliantów. Sukces został osiągnięty głównie dzięki pojawieniu się komunikacji cyfrowej i geniuszu ludzi pracujących w Bletchley Park, sekretnej siedziby w Anglii. Enigma mimo dobrej odporności na atak z ołówkiem i kartką jest całkiem łatwa do złamania przy pomocy cyfrowego komputera.

Enigma
Rys. 1 Enigma.

Enigma była maszyną opartą na rotorach, popularnej metodzie kryptografii w tamtych czasach. Rotor jest to odosobniony dysk, na którego krawędzi rozmieszczone są równomiernie metalowe styki, po jednym dla każdej litery alfabetu. Styki są umieszczone po obu stronach dysku. Każdy styk po jednej stronie jest połączony przewodnikiem z pewnym stykiem po drugiej stronie dysku. Umożliwia to przepływ prądu elektrycznego z określonego styku po jednej stronie na określony styk po drugiej stronie (Rysunek 2). Rysunek 3 przedstawia kompletny układ rotorów. Widać na nim, że Enigma posiada trzy rotory π0, π1, π2 oraz jeden rotor odwracający - πr.
Dwa rotory
Rys. 2 Widok dwóch rotorów.

Układ rotorów
Rys. 3 Kompletny układ rotorów.

Danymi wejściowymi dla enigmy jest łańcuch liter alfabetu bez pustych znaków. Każdy znak jest poddany następującym fazom:
  1. Litera wejściowa jest przekształcana przez permutację początkową IP.
  2. Znak wynikający z takiego przekształcenia zostaje przesłany przez rotory π0, π1 oraz π2
  3. Tak przekształcony znak jest przesyłany do rotora odbijającego - πr.
  4. Znak po odbiciu jest wysyłany kolejno na rotory π2, π1 oraz π0 (przechodzi przez rotory w przeciwnym kierunku).
  5. Przekształcony znak przekształcany jest przez permutację odwrotną do IP - IP-1.
Po przerobieniu znaku i przed pracą nad następnym znakiem każdy rotor może zostać obrócony o pewien kąt. W Enigmie rotor π0 jest obracany po każdym znaku o jeden w kierunku przeciwnym do ruchu wskazówek zegara. Kiedy π0 skończy jedną rundę (obróci się 26 razy), wtedy rotor π1 obraca się o jeden w tym samym kierunku. Podobnie rotor π2 obraca się o jeden kiedy π1 zrobi jedną rundę. πr obraca się kiedy π2 obróci się 26 razy. Oczywiście rotor πr obraca się najwolniej.
Procedura opisana powyżej może zostać użyta zarówno do kodowania jak i dekodowania znaków, pod warunkiem, że permutacja πr używana przez ostatni rotor jest inwolucją. Czyli, że x = πr(πr(x)). Można założyć, że ta zależność jest spełniona.
Klucz prywatny Enigmy składa się z (1) rotorów π0, π1, π2 i πr, (2) permutacji wstępnej IP i (3) początkowych przesunięć obrotowych k0, k1, k2, kr rotorów π0, π1, π2, πr. W Wermachcie rotory były zmieniane rzadko i były wybierane spośród czterech różnych rotorów.

Zadanie

Cofnąłeś się w czasie do Bletchley Park razem ze swoim laptopem i musisz pomóc odszyfrować kilka wiadomości, które zostały przechwycone w ciągu dnia. Dostaniesz kompletny tekst zaszyfrowany, fragment tekstu odszyfrowanego i fragment klucza prywatnego Enigmy. Twoim zadaniem jest znalezienie prawidłowego klucza i dokończenie dekodowania wiadomości.

Wejście

W pierwszej linii podana jest liczba testów. Każdy test rozpoczyna się od klucza prywatnego Enigmy. Klucz jest podany w kolejnych sześciu liniach. Pierwsze cztery opisują specyfikacje rotorów π0, π1, π2 oraz πr. Każda z nich to ciąg 26 małych liter alfabetu angielskiego. Znak na pozycji i-tej określa przyporządkowanie i-tego znaku w alfabecie (ciąg "bha..." oznacza, że "a" przechodzi na "b", "b" przechodzi na "h", "c" przechodzi na "a", ...). Fizycznie ciąg znaków podany jest w kierunku zgodnym z ruchem wskazówek zegara patrząc z przodu na stos rotorów π0, π1, π2 i πr. Po opisie rotorów, w piątej linii jest podana permutacja IP w podobny sposób. W szóstej linii podane są początkowe przesunięcia k0, k1, k2, kr rotorów π0, π1, π2 i πr. Podane one są jako ciąg czterech liter alfabetu angielskiego. Znak "a" określa że dany rotor jest w swojej oryginalnej pozycji, znak "b" określa że został przesunięty o jeden w normalny sposób, itd. Na przykład ciąg "dgaa" oznacza, ze π0 jest początkowo przesunięte o 3, π1 jest początkowo przesunięte o 6, a π2 i πr znajdują się na oryginalnych pozycjach. W dwóch kolejnych liniach po kluczu prywatnym znajdują się dwa ciągi złożone tylko z małych liter alfabetu angielskiego o długości od 1 do 80 znaków. Pierwszy z nich zawiera tekst odszyfrowany, a drugi zaszyfrowany. Tekst odszyfrowany oraz jakakolwiek część klucza prywatnego może być niekompletna - tzn. mogą się na pewnych miejscach pojawić znaki zapytania "?". Liczba znaków zapytania może być co najwyżej równa 3.

Wyjście

Dla każdego testu wypisz jedną linię zawierającą kompletną, odszyfrowaną wiadomość. Możesz założyć, że rozwiązanie zawsze istnieje i jest unikalne.

Przykładowe wejście

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

Przykładowe wyjście

manyorganizationsrelyoncomputers
acm