Infinite Compression Plan Consortium (ICPC) a développé une nouvelle et excellente stratégie de compression des données, appelée «Don’t Repeat Yourself» (DRY). DRY agit sur une chaîne de caractères : si elle contient deux occurrences consécutives d'une même sous-chaîne, il en supprime simplement une. Par exemple, dans «alfalfa seeds», il peut supprimer l'une des deux sous-chaînes «e» de «seeds», et l'une des deux sous-chaînes «lfa» de «alfalfa», ce qui donne «alfa seds». DRY peut aussi profiter des suppressions précédentes : dans «seventeenth baggage», par exemple, il supprime d'abord le «e» répété de «seventeenth» et le «g» répété de «baggage», obtenant «sevententh bagage», puis le «ent» répété de «sevententh» et le «ag» répété de «bagage», obtenant «seventh bage».

Image adaptée de Wikimedia Commons, domaine public

S'il existe plusieurs sous-chaînes répétées consécutives à supprimer, DRY doit choisir de manière à obtenir la chaîne finale la plus courte possible. Par exemple, dans «ABBCDCABCDCD», deux choix sont possibles : supprimer le «B» répété près du début, ou le «CD» répété à la fin. Si le «B» est supprimé, DRY peut ensuite supprimer le «ABCDC» répété, obtenant «ABCDCD», puis le «CD» final, obtenant «ABCD». En revanche, s'il supprime d'abord le «CD» final, il reste «ABBCDCABCD», dont seul le «B» répété peut être supprimé pour obtenir «ABCDCABCD» ; plus rien ne peut alors être supprimé. Le bon choix est donc de commencer par comprimer le double «B» et de finir avec «ABCD».

ICPC a observé que DRY donne les meilleurs résultats sur les chaînes binaires, c'est-à-dire composées uniquement de zéros et de uns. Il vous a donc chargé d'implémenter le meilleur algorithme DRY possible pour les chaînes binaires. Pour toute chaîne binaire, vous devez afficher une chaîne de longueur minimale pouvant être obtenue en lui appliquant DRY de façon répétée.

Entrée

L'entrée consiste en une seule ligne contenant une chaîne non vide de longueur inférieure ou égale à $10^5$, composée uniquement de zéros et de uns.

Sortie

Affichez une ligne contenant un résultat de longueur minimale de l'application de DRY à la chaîne d'entrée. S'il existe plusieurs résultats de longueur minimale, n'importe lequel sera accepté.

Exemples

Entrée 1

1111

Sortie 1

1

Entrée 2

101

Sortie 2

101

Entrée 3

10110

Sortie 3

10