Infinite Compression Plan Consortium (ICPC) разработал новую замечательную стратегию сжатия данных под названием «Don’t Repeat Yourself» (DRY). DRY работает со строкой символов: если в ней есть два последовательных вхождения одной и той же подстроки, одно из них просто удаляется. Например, в строке «alfalfa seeds» можно удалить одну из двух подстрок «e» в «seeds» и одну из двух подстрок «lfa» в «alfalfa», получив «alfa seds». DRY может использовать и результаты предыдущих удалений: например, в «seventeenth baggage» сначала удаляются повторяющиеся «e» в «seventeenth» и «g» в «baggage», получается «sevententh bagage», затем повторяющиеся «ent» в «sevententh» и «ag» в «bagage», получается «seventh bage».
Изображение адаптировано из Wikimedia Commons, общественное достояние
Если есть несколько вариантов удаления последовательных повторяющихся подстрок, DRY должен выбирать так, чтобы итоговая строка была как можно короче. Например, в «ABBCDCABCDCD» есть два варианта: удалить повторяющуюся «B» вблизи начала или повторяющуюся «CD» в конце. Если удалить «B», затем можно удалить повторяющуюся «ABCDC» и получить «ABCDCD», после чего удалить конечную «CD», получив «ABCD». Но если сначала удалить конечную «CD», останется «ABBCDCABCD», из которой можно удалить лишь повторяющуюся «B», получив «ABCDCABCD», а из этой строки больше ничего удалить нельзя. Поэтому правильный выбор — начать со сжатия двойной «B» и в итоге получить «ABCD».
ICPC заметил, что DRY даёт лучшие результаты на двоичных строках, то есть строках только из нулей и единиц. Поэтому вам поручили реализовать наилучший алгоритм DRY для двоичных строк. Для любой двоичной строки вы должны вывести кратчайшую строку, которую можно получить многократным применением DRY.
Входные данные
Ввод состоит из одной строки, содержащей непустую строку длины не более $10^5$, состоящую только из нулей и единиц.
Выходные данные
Выведите одну строку, содержащую кратчайший возможный результат применения DRY к входной строке. Если кратчайших результатов несколько, принимается любой из них.
Примеры
Входные данные 1
1111
Выходные данные 1
1
Входные данные 2
101
Выходные данные 2
101
Входные данные 3
10110
Выходные данные 3
10