Infinite Compression Plan Consortium (ICPC) ha desarrollado una nueva y excelente estrategia de compresión de datos llamada «Don’t Repeat Yourself» (DRY). DRY actúa sobre una cadena de caracteres y, si esta contiene dos apariciones consecutivas de la misma subcadena, simplemente elimina una de ellas. Por ejemplo, en «alfalfa seeds» podría eliminar una de las dos subcadenas «e» de «seeds» y una de las dos subcadenas «lfa» de «alfalfa», obteniendo «alfa seds». DRY también puede aprovechar eliminaciones anteriores: por ejemplo, en «seventeenth baggage» primero eliminará la «e» duplicada de «seventeenth» y la «g» duplicada de «baggage», obteniendo «sevententh bagage», y luego el «ent» duplicado de «sevententh» y el «ag» duplicado de «bagage», obteniendo «seventh bage».
Imagen adaptada de Wikimedia Commons, dominio público
Si hay varias subcadenas consecutivas repetidas que se pueden eliminar, DRY debe elegir de modo que la cadena final sea lo más corta posible. Por ejemplo, en «ABBCDCABCDCD» tiene dos opciones: eliminar la «B» repetida cerca del inicio o el «CD» repetido al final. Si elimina la «B», podrá eliminar después el «ABCDC» repetido, obteniendo «ABCDCD», del que finalmente eliminará el «CD» del final para obtener «ABCD». Sin embargo, si primero elimina el «CD» del final, quedará «ABBCDCABCD», del que solo puede eliminarse la «B» repetida para obtener «ABCDCABCD», y de esa cadena ya no puede eliminarse nada más. Por tanto, la elección correcta es comenzar comprimiendo la doble «B» y terminar con «ABCD».
ICPC observó que DRY obtiene los mejores resultados en cadenas binarias, es decir, cadenas compuestas solo de ceros y unos. Por ello, te ha encargado implementar el mejor algoritmo DRY posible para cadenas binarias. Para cualquier cadena binaria, debes imprimir una cadena de longitud mínima que pueda obtenerse aplicando DRY repetidamente.
Entrada
La entrada consiste en una sola línea que contiene una cadena no vacía de longitud menor o igual que $10^5$, formada únicamente por ceros y unos.
Salida
Imprime una línea con un resultado de longitud mínima de aplicar DRY a la cadena de entrada. Si hay varios resultados mínimos posibles, se aceptará cualquiera de ellos.
Ejemplos
Entrada 1
1111
Salida 1
1
Entrada 2
101
Salida 2
101
Entrada 3
10110
Salida 3
10