D. Вам знакомо это слово?
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Подстрока строки — это непрерывная подпоследовательность символов данной строки. Таким образом, строка bca является подстрокой строки abcabc, а строка cc — нет.

Повторяющийся блок — это строка, полученная конкатенацией некоторой строки с собой же. Таким образом, строка abcabc — это повторяющийся блок, а строки abcabd, ababab — нет.

Вам дана последовательность символов латинского алфавита (строка). За один ход Вы находите наикратчайшую подстроку, которая является повторяющимся блоком. Если таких подстрок несколько, выбираете ближайшую к левому краю строки. Пусть найденная подстрока имеет вид XX (X — некоторая строка), тогда Вы заменяете ее строкой X, иными словами, Вы удаляете одну из подстрок X в этой подстроке. Вы повторяете процесс до тех пор, пока в строке не остается повторяющихся блоков.

Как будет выглядеть результирующая строка? Посмотрите пояснения к тестовым примерам, чтобы лучше понять условие.

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

В первой строке дана строка, состоящая из строчных символов латинского алфавита, длины от 1 до 50000, включительно.

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

Выведите итоговую строку после применения операций.

Примеры
Входные данные
abccabc
Выходные данные
abc
Входные данные
aaaabaaab
Выходные данные
ab
Входные данные
birdbirdbirdistheword
Выходные данные
birdistheword
Примечание

В первом примере строка превращается так: abccabc  →  abcabc  →  abc.

Во втором примере строка превращается так: aaaabaaab  →  aaabaaab  →  aabaaab  →  abaaab  →  abaab  →  abab  →  ab.