Слабіше, ніж планувалось
Члени оргкомітету конкурсу з програмування у Кітошимі вирішили використовувати криптографічне програмне забезпечення для своїх секретних повідомлень. Вони попросили компанію Kodai Software розробити для цього криптографічне програмне забезпечення, яке повинно використовувати дуже складний математичний шифр.
Згідно аналізу повідомлень про виконання ІТ-проектів, багато з проектів не було виконано або своєчасно, або в рамках бюджету, або з потрібними характеристиками та функціями. Це ж відноситься і до цього випадку. Kodai Software не виконала розробку складного шифру до призначеного терміну поставки, і компанією було запропоновано використовувати на даний момент більш простіший варіант, у якому використовувався для шифрування спосіб заміщення. Природньо, що члени оргкомітету були незадоволені таким рішенням і настійно просили доставити їм повну специфікацію продукту, але за відсутністю іншого програмного забезпечення вони з небажанням все ж вирішили використовувати той програмний продукт, який їм було поставлено на даний момент.
У подальшому ми будемо називати текст перед шифруванням заданим, а текст, отриманий після шифрування, - зашифрованим.
Використовується простий шифр заміни букв у тексті, і його правило заміни задається множиною пар. Пара складається з двох неупорядкованих літер, тобто порядок літер у парі не має значення. Це означає, що пара (A, B) і пара (B, A) мають однаковий зміст. У одному правилі заміщення одна літера може опинитись не більше ніж в одній парі. Коли у тексті появляється якась літера з цієї пари, вона замінюється іншою літерою у цій парі. Літери, не вказані у специфікації пар, залишаються незмінними.
Наприклад, для заданого тексту
ABCDEFGHIJKLMNOPQRSTUVWXYZ
використання правила заміни f{(A, Z), (B, Y)} приводить до наступного зашифрованого тексту:
ZYCDEFGHIJKLMNOPQRSTUVWXBA
Це може бути великим шансом для нас, так як правила заміни здаються слабо захищеними від зламу. Можливо, ми зможемо взнати деякі зв'язки від членів оргкомітету. Ваша задача полягає у розробці програми розшифровки, яка зчитує зашифрований текст і виводить задане повідомлення.
Зашифроване повідомлення складається з одного чи декількох слів зашифрованого тексту. Слово зашифрованого тексту створюється із слова заданого тексту застосуванням правил підстановки. У вас є список кандидатів слів, який містить слова, що можуть появитися у тексті, ніяких іншиих слів у тексті появитися не може. Деякі слова зі списку можуть не використовуватись у тексті.
Гарантується, що завжди існує хоча б одна послідовність кандидатів слів, згідно яких зашифрований текст із заданого отримуєть застосуванням деякого правила підстановки. Врахуйте, що можуть бути випадки, коли неможливо однозначно визначити початковий текст за наявним зашифрованим текстом та списком кандидатів слів.
Вхідні дані
Вхідні дані складаються з декількох наборів даних, кожен з яких містит зашифрований текст повідомлення та список кандидатів слів у наступному форматі.
n word1 . . . wordn sequence
n у першому рядку задає ціле додатнє число, яке вказує кількість кандидатів слів. Кожен з наступних n рядків є одним з кандидатів слів. У останньому рядку набору задано зашифровану послідовність, яка складається з послідовності одного чи декількох слів, відкремлених одним пропуском і завершується крапкою.
Можете вважати, що кількість символів у кожній послідовності більше 1 і менше чи дорівнює 80, включаючи пропуски та крапку. Кількість кандидатів слова у списку не перевищує 20. Лише 26 прописних літер, від A до Z, використовуються у словах і довжина кожного слова від 1 до 20 включно.
Рядок з одного нуля означає завершення вхідних даних.
Для кожного набору вхідних даних ваша програма повинна у окремому рядку надрукувати розшифроване повідомлення. Два суміжних слова у рядку виведення повинні бути відокремлені одним пропуском, останнє слово повинно супроводжуватись крапкою і переведенням рядка. Якщо неможливо однозначно визначити початковий текст, рядок на виході повинен містити один дефіс, за яким відразу ж йде крапка.