Шифр Плейфера
Шифр Плейфера — це ручний симетричний метод шифрування, який став першим шифром заміни діграфів. Його розробив Чарльз Вітстон у 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'), або пробілом. Жоден рядок не починатиметься і не закінчуватиметься пробілом.
Вихідні дані
Вихід повинен бути одним рядком, що містить зашифрований текст, у верхньому регістрі. У виході не повинно бути пробілів.