Úloha: Šifrovaný text

Obdrželi jsme zašifrovanou zprávu, kterou máme rozšifrovat. Díky činnosti zpravodajů máme k dispozici dodatečné informace, které nám pomohou zjistit text zprávy. Víme, že šifra je neobyčejně jednoduchá, je to pouze permutace 26 písmen anglické abecedy. To ale samo o sobě dosti dobře nestačí. Permutací 26 prvků je 26! = 403291461126605635584000000, což je alespoň tisíckrát více než počet hvězd v pozorovatelném vesmíru. Nelze tedy počítat s tím, že bychom vyzkoušeli všechny permutace a vybrali tu, která produkuje srozumitelný text. Podařilo se však získat kompletní seznam všech slov (slovník), které se vůbec mohou v jakékoli zprávě před jejím zašifrováním vyskytnout. Je tedy jisté, že v zašifrované zprávě existuje ke každému zašifrovanému slovu jeho protějšek ve slovníku. Takto vybaveni již můžeme přistoupit k dešifrování. Je možné, protože šifru neznáme, že danou zašifrovanou zprávu lze pomocí slovníku interpretovat více způsoby.

Pro šfrovanou i dešifrovanou zprávu se používá pouze 26 znaků malé anglické abecedy a znak mezera.

Vstup

Na vstupu je nejprve řádek s celým kladným číslem udávajícím počet slov ve slovníku. Dále následuje seznam všech slov ve slovníku, na každém řádku jedno slovo. Slova mohou být uvedena v libovolném pořadí. Za seznamem na dalším řádku je uveden text šifrované zprávy. Řádek neobsahuje počáteční ani koncové mezery, slova v šifrovaném textu jsou oddělena jedinou mezerou, jiné mezery vstup neobsahuje. Vstup neobsahuje prázdné řádky. Délka každého slova je nejvýše 30 znaků, slovník obsahuje nejvýše 100 000 slov. Všechna slova ve slovníku jsou navzájem různá. Zpráva má nejvýše 100 000 slov.

Výstup

Na výstupu je seznam všech možných variant dešifrované (= původní) zprávy, seřazený ve vzrůstajícím abecedním pořadí. Každá varianta je uvedena na samostatném řádku a je formátována stejně jako šifrovaná zpráva. Pokud zprávu s použitím slovníku dešifrovat nelze, obsahuje výstup jediný řádek s textem Cannot be decoded bez úvodních a koncových mezer. Výstup neobsahuje prázdné řádky.

Příklad 1

Vstup:
8
dog
six
is
no
joe
hat
has
fat
kpz ift op ifu
Výstup:
dog has no hat
dog hat no has
joe has no hat
joe hat no has

Příklad 2

Vstup:
6
what
whale
star
start
ships
float
stay tuned
Výstup:
Cannot be decoded

Testovací data

Veřejná data k úloze jsou k dispozici. Veřejná data jsou uložena také v odevzdávacím systému a při každém odevzdání/spuštění úlohy dostává řešitel kompletní výstup na stdout a stderr ze svého programu pro každý soubor veřejných dat.

b

Veřejná data