Проникновение
Юный пиратский капитан Джек Альбатрос тайно бросил якорь в скрытой бухте недалеко от ПортВайн, местной точки встречи закаленных пиратов и обитателей моря. Замаскировавшись под посыльного, вы проникли на службу к грозному легендарному капитану Стиви, и вам поручено доставлять небольшие зашифрованные сообщения между капитаном Стиви и его командой. Ваша задача — взломать шифровку сообщений, чтобы помочь молодому капитану Альбатросу получить столь необходимое преимущество в его стремлении к славе с деревянной ногой. К счастью, вы (в отличие от капитана Альбатроса) уже давно в этом деле и знаете, какие слова ожидать в пиратских посланиях. Ниже приведена таблица часто встречающихся слов:
"be" "our" "rum" "will"
"dead" "hook" "ship" "blood"
"sable" "avenge" "parrot" "captain"
В шифре подстановки (смешанный алфавит) каждая буква открытого текста заменяется на другую, в данном случае произвольную, но уникальную, букву из алфавита. Дано зашифрованное текстовое сообщение с использованием шифра подстановки и данный набор из двенадцати известных слов выше. Ваша задача — расшифровать зашифрованный текст и предоставить нам и капитану Альбатросу открытый текст. Это возможно, если и только если существует уникальное отображение подстановки от зашифрованных букв к буквам открытого текста, такое что:
Подмножество S из двенадцати слов появляется в открытом тексте, и
Количество различных букв в словах из S равно количеству различных букв в зашифрованном тексте.
Обратите внимание, что не все известные слова могут присутствовать в открытом тексте и что замены не являются взаимными ('a' зашифровано как 'h' НЕ обязательно означает, что 'h' зашифровано как 'a').
Входные данные
Текст, зашифрованный с помощью шифра подстановки.
Зашифрованный текст дан в одной строке, содержащей не более 200 символов из множества ['a'-'z',' ']. Только буквы ['a'-'z'] открытого текста зашифрованы, пробелы остаются незашифрованными.
Выходные данные
Расшифрованный открытый текст, если это возможно, или строка "Impossible", если текст невозможно уникально расшифровать, используя набор известных слов.