Задача B. Криптоаналитика за еду ≡

Условие

Начинающий программист Коля заинтересовался криптографией. Изучая различные алгоритмы шифрования, ему захотелось придумать свой собственный. Недолго подумав, он нарисовал табличку, которая выглядит следующим образом:

На основании неё он построил следующий алгоритм: в каждом слове последовательно выбирается буква W₁ и соответствующая ей строка таблицы, затем берется следующая за ней буква W₂ и соответствующий ей столбец, и после этого W₁ шифруется символом, находящимся на пересечении выбранных строки и столбца. Так продолжается до последней буквы, которая шифруется с помощью первой буквы уже зашифрованного слова. К примеру, строка "HELLO" после шифрования запишется как "LPWZZ".

Используя данный алгоритм, Коля зашифровал небольшое сообщение и отправил его своему другу Никите. Коля пообещал целый месяц платить в столовой за своего друга, если Никита сможет расшифровать данное сообщение до вечера того же дня.

Помогите Никите узнать, что же за текст скрывается в этом странном сообщении.

Формат входного файла

Первая строка входного файла содержит строку S — зашифрованное сообщение. Длина строки не превосходит 10⁵ и состоит только из заглавных букв латинского алфавита A-Z (ASCII 65-90).

Формат выходного файла

Выходной файл должен содержать строку с расшифрованным сообщением.

Ограничения

2 ≤ N ≤ 10⁵, где N — длина строки.

Примеры тестов

LPWZZ

HELLO