SPOJ in Gyumri

   Учитель истории Владимир Иванович очень любит археологические находки. Однажды, посещая один из музеев Рима, он прочитал представленное на стенде, посвященном тайной переписке императора Цезаря с прекрасной царицей Египта Клеопатрой, письмо, содержание которого показалось ему бессмысленным (хотя подумал, что письмо написано на латыни).

   Вернувшись из путешествия, учитель поделился впечатлениями о посещении данного музея с коллегой – учителем информатики Василием Петровичем, который рассказал, что однажды ему попалась интересная научная заметка о том, что все свои сообщения император Цезарь шифровал. Историки назвали этот метод шифрования – «Шифр Цезаря», суть которого состоит в следующем. На двух дисках (внешнем и внутреннем) расположены все символы латинского алфавита в алфавитном порядке. До начала шифрования выбирается некоторое расположение внутреннего диска относительно внешнего таким образом, чтобы каждая буква внешнего диска переходила в одну букву внутреннего (на рисунке буква «A» переходит в букву «T», а буква «G» в букву «Z»). После этого все символы сообщения заменяются в соответствии с выбранным расположением дисков, при этом заглавные буквы переходят в заглавные, а строчные – в строчные, пробелы и знаки препинания остаются на своих местах. Например, если диски расположены как на рисунке, то сообщение «Hello» будет зашифровано в сообщение «Axeeh».

   Владимир Иванович показал коллеге сделанный в музее снимок письма (зашифрованного «Шифром Цезаря» сообщения), и они решили расшифровать его. Применив множество способов расшифровки, только один из них позволил получить текст, непохожий на бессвязный набор букв. Оказалось, что из всех возможных результатов расшифровки, правильным был минимальный лексикографически.

   Расшифровка тайного письма показалась Василию Петровичу очень полезным упражнением по информатике. Он просит Вас – лучшего ученика, написать программу, которая будет находить минимальную лексикографически расшифровку текста.

Входные данные.

   Единственная строка содержит строковую величину S (1 ≤ |S| ≤ 1 000 000), включающую строчные и заглавные символы латинского алфавита, пробелы (ASCII 32) и точки (ASCII 46). Гарантируется, что строковая величина S не начинается и не заканчивается символом пробела.

Выходные данные.

   Одну строковую величину длины |S| — расшифрованное сообщение.

Примеры.