URI Online Judge | 2176

Paridad

Por Cristhian Bonilha, UTFPR BR Brazil

Timelimit: 1

La popularidad de las redes WiFi incrementó la tasa de pérdida de datos que se están transfiriendo, debido a que varios factores de entorno pueden fácilmente comprometer los datos durante el tráfico. El objetivo principal de URI, Unidad de Recuperación de Información, es identificar y corregir errores en los mensajes que se están enviando a través de redes WiFi.

La técnica usada por URI para identificar errores es el test de paridad, el cual puede ser descrito como sigue: Sea S un mensaje que va a ser enviado desde un dispositivo a otro. Antes de que S se envíe, se agrega un bit extra B al final de la representación binaria de S. Si S tiene un número par de valores 1, el bit extra B tendrá valor 0. De otra forma, si S tiene un número impar de bits con valor 1, B tendrá valor 1. De esta forma, luego de insertar el bit B, el mensaje S siempre tendrá un número par de valores 1.

Cuando el receptor recibe el mensaje S, él cuenta cuantos bits con valor 1 hay. Si la cantidad es par, significa que el mensaje fué transferido correctamente. De otra forma, significa que el mensaje tuvo una modificación y no es correcto.

Tu tarea es escribir un algoritmo que haga la inserción del bit extra B en el mensaje S, asegurando que luego de la inserción el mensaje S tiene un número par de bits de valor 1.

Entrada

Cada caso de prueba consiste de una línea conteniendo el mensaje S, el cual tiene al menos 1 y como máximo 100 bits.

Salida

Imprima una línea con el mensaje S con el bit extra B.

Ejemplos de entrada Ejemplos de salida

10

101

000110

0001100

0

00