Слабее, чем планировалось
Члены оргкомитета конкурса программирования в Китошиме решили использовать криптографическое программное обеспечение для своих секретных сообщений. Они попросили компанию 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 включительно.
Строка из одного нуля означает окончание входных данных.
Выходные данные
Для каждого набора входных данных ваша программа должна в отдельной строке напечатать расшифрованное сообщение. Два смежных слов в строке вывода должны быть разделены одним пробелом, последнее слово должно сопровождаться точкой и переводом строки. Если невозможно однозначно определить исходный текст, строка на выходе должен содержать один дефис, за которым сразу следует точка.