Das Infinite Compression Plan Consortium (ICPC) hat eine großartige neue Datenkompressionsstrategie namens „Don’t Repeat Yourself“ (DRY) entwickelt. DRY arbeitet auf einer Zeichenkette: Enthält sie zwei unmittelbar aufeinanderfolgende Vorkommen derselben Teilzeichenkette, wird eines davon einfach entfernt. Beispielsweise kann in „alfalfa seeds“ eines der beiden „e“ in „seeds“ und eines der beiden „lfa“ in „alfalfa“ entfernt werden, sodass „alfa seds“ entsteht. DRY kann auch frühere Entfernungen ausnutzen: In „seventeenth baggage“ entfernt es zunächst das doppelte „e“ in „seventeenth“ und das doppelte „g“ in „baggage“, wodurch „sevententh bagage“ entsteht, und anschließend das doppelte „ent“ in „sevententh“ und das doppelte „ag“ in „bagage“, wodurch „seventh bage“ entsteht.
Bild nach Wikimedia Commons, gemeinfrei
Wenn mehrere aufeinanderfolgend wiederholte Teilzeichenketten entfernt werden können, soll DRY so wählen, dass die endgültige Zeichenkette möglichst kurz ist. Bei „ABBCDCABCDCD“ gibt es beispielsweise zwei Möglichkeiten: das wiederholte „B“ nahe dem Anfang oder das wiederholte „CD“ am Ende zu entfernen. Wird „B“ entfernt, kann DRY danach das wiederholte „ABCDC“ entfernen und erhält „ABCDCD“. Daraus wird schließlich das „CD“ am Ende entfernt, sodass „ABCD“ entsteht. Entfernt DRY jedoch zuerst das „CD“ am Ende, bleibt „ABBCDCABCD“. Daraus kann nur noch das wiederholte „B“ entfernt werden, um „ABCDCABCD“ zu erhalten, und aus dieser Zeichenkette lässt sich nichts mehr entfernen. Richtig ist daher, mit der Kompression des doppelten „B“ zu beginnen und schließlich „ABCD“ zu erhalten.
ICPC beobachtete, dass DRY auf binären Zeichenketten, also Zeichenketten nur aus Nullen und Einsen, die besten Ergebnisse liefert. Daher sollst du den bestmöglichen DRY-Algorithmus für binäre Zeichenketten implementieren. Gib für jede binäre Zeichenkette eine kürzeste Zeichenkette aus, die durch wiederholtes Anwenden von DRY entstehen kann.
Eingabe
Die Eingabe besteht aus einer Zeile mit einer nichtleeren Zeichenkette der Länge höchstens $10^5$, die nur aus Nullen und Einsen besteht.
Ausgabe
Gib eine Zeile mit einem kürzestmöglichen Ergebnis der Anwendung von DRY auf die Eingabezeichenkette aus. Gibt es mehrere kürzeste Ergebnisse, wird jedes davon akzeptiert.
Beispiele
Eingabe 1
1111
Ausgabe 1
1
Eingabe 2
101
Ausgabe 2
101
Eingabe 3
10110
Ausgabe 3
10