Покорение вселенной

Два сообщества А и В начали делить пространство вселенной, устанавливая свой флаг на звездах и планетах. Сообщество А составило маршрут покорения вселенной, состоящий из названий объектов (планет и звезд) в порядке их посещения. Названия объектов состояли из английских букв и начинались с заглавной буквы, все остальные буквы – строчные. Маршрут представляет собой непрерывную цепочку символов, т.к. названия объектов записывались подряд без пробелов. Строка маршрута была зашифрована перестановками групп символов, сформированных из исходной цепочки. Первая группа включает первую букву цепочки. Вторая группа формируется из двух последних букв исходной цепочки в порядке их встречаемости, если они не попали в первую группу. Третья группа – из трех символов от начала цепочки, не вошедших в ни какую группу. Четвертая – из четырех символов от конца цепочки, также пока не включенных в другие группы и т.д. (рис.1). Формирование групп заканчивается, когда каждый символ цепочки включен в какую-либо группу. Если в момент завершения формирования групп последняя группа не набирает требуемое количество символов, то в нее включаются оставшиеся символы, не вошедшие ни в какую группу. Каждый символ принадлежит только одной группе.

При шифровании первая группа символов меняется местами со второй группой, третья группа с четвертой и т.д. Если сформировалось нечетное количество групп, то последняя группа ставится на свободное место, образовавшееся внутри шифруемой строки (рис.2). Приведенный метод шифрования гарантирует, что длина зашифрованной строки всегда равна длине исходной строки.

Сообществу В удалось перехватить маршрут сообщества А. Но его слабые технические возможности не позволяют существенно нарушить планы соперников, поэтому сообществом В был составлен маршрут, включающий только те объекты, которые в исходном маршруте сообщества А находятся в позициях, соответствующих простым числам. Формально, если маршрут сообщества A состоит из объектов p₁p₂p₃…p_n, то маршрут сообщества B будет иметь вид p_i1p_i2p_i3…p_im, где i_k – простое число, 1 < i_k ≤ n, 1 ≤ k ≤ m, i_k < i_k+1.

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

Входной файл INPUT.TXT содержит строку, представляющую зашифрованный маршрут сообщества A, содержащий от 1 до 500 000 символов.

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

В выходной файл OUTPUT.TXT выведите строку, содержащую маршрут посещения планет и звезд сообществом В. Если в результате формирования получился пустой маршрут, не содержащий ни одного объекта, то в выходной файл следует вывести слово «Impossible» (без кавычек).

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]