题目描述

无限压缩计划联盟（Infinite Compression Plan Consortium, ICPC）开发出了一种全新的，伟大的数据压缩策略，称作「不要重复自己」（Don't Repeat Yourself, DRY）。DRY 适用于字符串，如果字符串中包含连续两个相同的子串，它就会删除其中一个。例如，在字符串 alfalfa seeds 中，它可以移除子串 seeds 中两个 e 中的一个，和子串 alfalfa 中两个 lfa 中的一个，结果为 alfa seds。DRY 也可以利用之前的删除操作——例如，在字符串 seventeenth baggage 中，首先会移除 seventeenth 中重复的 e 和 baggage 中重复的 g，得到 sevententh bagage，然后删除 sevententh 中重复的 ent 和 bagage 中重复的 ag，得到 seventh bage。

如果有多种删除连续重复子串的方法，DRY 会选择可以得到最短的最终子串的删除方法。例如，对于字符串 ABBCDCABCDCD，DRY 有两种选择——要么删除靠近开头的两个重复的 B 中的一个，或者删除结尾处重复的 CD。如果删除了 B，则 DRY 就可以删除重复的 ABCDC，获得 ABCDCD，然后就可以删除结尾的 CD，最终得到 ABCD。然而，如果 DRY 首先移除了结尾的 CD，首先会得到 ABBCDCABCD，这样只能删除连续的 B，得到 ABCDCABCD——这个字符串不能移除更多字符了。因此，对于 DRY 来说正确的选择是先压缩两个 B，然后得到 ABCD。

ICPC 观察到 DRY 在二进制串上能得到最佳结果——也就是只包含 0 和 1 的字符串。因此，因此，你的任务就是在二进制字符串上实现最佳的 DRY 算法。对于任意二进制串，你都应该输出一个通过反复使用 DRY 算法可以得到的最短字符串。

输入格式

一行一个非空字符串，长度小于等于 $10^5$，且仅包含 0 和 1。

输出格式

输出一行，表示对输入字符串进行 DRY 算法后获得的最短可能字符串。如果有多于一种可能的结果，输出任意一种均可。

1111

1

101

101

10110

10