Infinite Compression Plan Consortium (ICPC) opracowało nową, znakomitą strategię kompresji danych o nazwie „Don’t Repeat Yourself” (DRY). DRY działa na ciągu znaków: jeśli zawiera on dwa kolejne wystąpienia tego samego spójnego fragmentu, usuwa jedno z nich. Na przykład w ciągu „alfalfa seeds” można usunąć jedno z dwóch wystąpień „e” w „seeds” i jedno z dwóch wystąpień „lfa” w „alfalfa”, otrzymując „alfa seds”. DRY może też korzystać z wcześniejszych usunięć: na przykład w „seventeenth baggage” najpierw usuwa powtórzone „e” w „seventeenth” oraz „g” w „baggage”, otrzymując „sevententh bagage”, a następnie powtórzone „ent” w „sevententh” oraz „ag” w „bagage”, otrzymując „seventh bage”.
Ilustracja zaadaptowana z Wikimedia Commons, domena publiczna
Jeżeli można usunąć różne powtarzające się kolejne spójne fragmenty, DRY powinno wybrać tak, aby końcowy ciąg był jak najkrótszy. Na przykład dla „ABBCDCABCDCD” istnieją dwie możliwości: usunięcie powtórzonego „B” blisko początku albo powtórzonego „CD” na końcu. Po usunięciu „B” można usunąć powtórzone „ABCDC”, uzyskując „ABCDCD”, a następnie końcowe „CD”, uzyskując „ABCD”. Jeśli jednak DRY najpierw usunie końcowe „CD”, pozostanie „ABBCDCABCD”, z którego można usunąć tylko powtórzone „B”, otrzymując „ABCDCABCD” — i z tego ciągu nie da się już nic usunąć. Właściwym wyborem jest więc rozpoczęcie od kompresji podwójnego „B”, aby ostatecznie otrzymać „ABCD”.
ICPC zauważyło, że DRY daje najlepsze wyniki dla ciągów binarnych, czyli złożonych tylko z zer i jedynek. Zleciło ci zatem zaimplementowanie najlepszego możliwego algorytmu DRY dla ciągów binarnych. Dla dowolnego takiego ciągu należy wypisać najkrótszy ciąg, jaki można uzyskać przez wielokrotne stosowanie DRY.
Wejście
Wejście składa się z jednego wiersza zawierającego niepusty ciąg długości co najwyżej $10^5$, złożony wyłącznie z zer i jedynek.
Wyjście
Wypisz jeden wiersz zawierający najkrótszy możliwy wynik zastosowania DRY do ciągu wejściowego. Jeśli istnieje wiele najkrótszych wyników, zaakceptowany zostanie dowolny z nich.
Przykład
Wejście 1
1111
Wyjście 1
1
Wejście 2
101
Wyjście 2
101
Wejście 3
10110
Wyjście 3
10