Compression

The Infinite Compression Plan Consortium (ICPC) has developed a new compression strategy called “Don’t Repeat Yourself” (DRY). DRY works on a string of characters. If the string contains two consecutive instances of the same substring, DRY removes one of them. For example, in the string alfalfa seeds, DRY can remove one of the two e substrings in seeds, and one of the two lfa substrings in alfalfa, resulting in alfa seds. DRY can also use earlier removals. In the string seventeenth baggage, DRY first removes the duplicate e in seventeenth and the duplicate g in baggage, resulting in sevententh bagage. Then it removes the duplicate ent in sevententh and the duplicate ag in bagage, resulting in seventh bage.

If DRY has several choices of repeated consecutive substrings to remove, it chooses the one that gives the shortest possible final string. For example, in ABBCDCABCDCD, DRY can remove the repeated B near the beginning, or the repeated CD at the end. If DRY removes the B, it can then remove the repeated ABCDC, resulting in ABCDCD, and finally remove the CD at the end, resulting in ABCD. If DRY removes the CD at the end first, the string becomes ABBCDCABCD. Only the repeated B can be removed from there, giving ABCDCABCD, and nothing more can be removed. So the correct first step is to compress the double B.

ICPC observed that DRY works best on binary strings, which are strings made only of zeroes and ones. ICPC asks you to implement the best possible DRY algorithm for binary strings. For any binary string, output a shortest string that can be obtained by repeatedly applying DRY to it.

The input consists of a single line containing a nonempty string of length at most $10^5$, made only of zeroes and ones.

Output one line containing a shortest possible result of running DRY on the input. If more than one shortest result is possible, any one is accepted.