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