Шифр Плейфера
Шифр Плейфера — это ручной симметричный метод шифрования и первый шифр, использующий замену биграмм. Схема была изобретена в 1854 году Чарльзом Уитстоном, но названа в честь лорда Плейфера, который популяризировал её использование.
Шифр Плейфера использует таблицу размером 5 на 5, в которой каждая буква английского алфавита встречается ровно один раз (за исключением 'Q', которая отсутствует). Эта таблица служит ключом шифрования. Чтобы её легче было запомнить, таблицу обычно создают на основе ключевой фразы. Сначала заполняют таблицу буквами ключевой фразы (пропуская пробелы и повторяющиеся буквы), затем оставшиеся ячейки заполняют остальными буквами алфавита по порядку. Ключевая фраза записывается в верхних рядах таблицы слева направо. Например, если ключевая фраза "playfair example", ключ шифрования будет выглядеть так:
Чтобы зашифровать сообщение, удалите все пробелы и разбейте сообщение на биграммы (группы из 2 букв), так что, например, "Hello World" становится "HE LL OW OR LD". Затем используйте таблицу ключей и примените следующее правило для каждой пары букв:
Если обе буквы одинаковы (или осталась только одна буква), добавьте 'X' после первой буквы. Зашифруйте новую пару и продолжайте (обратите внимание, что это изменяет все последующие биграммы).
Если буквы находятся в одном ряду таблицы, замените их буквами, находящимися непосредственно справа от них (оборачивая влево, если буква в исходной паре была на правом краю ряда). С таблицей выше биграмма 'CH' будет зашифрована как 'DB'.
Если буквы находятся в одном столбце таблицы, замените их буквами, находящимися непосредственно ниже них (оборачивая наверх, если буква в исходной паре была на нижнем краю столбца). С таблицей выше биграмма 'VA' будет зашифрована как 'AE'.
Если буквы не находятся в одном ряду или столбце, замените их буквами в том же ряду, но на противоположных углах прямоугольника, образованного исходной парой. Порядок важен: первая буква зашифрованной пары — это та, которая находится в том же ряду, что и первая буква исходной пары. С таблицей выше биграмма 'KM' будет зашифрована как 'SR'.
Напишите программу, которая считывает ключевую фразу и открытый текст для шифрования и выводит зашифрованный текст.
Текст для шифрования не будет содержать две 'x' подряд или 'x' в качестве последнего символа, чтобы избежать бесконечного повторения первого правила.
Входные данные
Вход содержит две строки. Первая строка содержит ключевую фразу. Вторая строка содержит текст для шифрования. Каждая строка будет содержать от 1 до 1000 символов включительно. Каждый символ будет строчной буквой английского алфавита, 'a' - 'z' (кроме 'q'), или пробелом. Ни одна строка не будет начинаться или заканчиваться пробелом.
Выходные данные
Вывод должен быть одной строкой, содержащей зашифрованный текст, в верхнем регистре. В выводе не должно быть пробелов.