Usted tal vez conoce el Juego de la Vida de Conway, el cual es un conjunto de reglas para celdas de una grilla que puede producir configuraciones increíblemente complejas. En este problema trataremos con una versión simplificada del juego.

Hay una tirilla unidimensional circular de ~N~ celdas. Las celdas están enumeradas desde ~1~ hasta ~N~ de forma que la celda ~1~ y la celda ~2~ son adyacentes, la celda ~2~ y la ~3~ son adyacentes y así hasta la celda ~N-1~ la cual es adyacente con la celda ~N~. Como la tirilla es circular, la celda ~1~ es adyacente con la celda ~N~.

Cada celda es un organismo vivo (representado por 1) o muerto (representado por 0). Las celdas cambian por generaciones. Si exactamente una de las celdas vecinas está viva en la generación actual, entonces vivirá para la próxima generación. En caso contrario la celda estará muerta en la próxima generación.

Dado el estado inicial de la tirilla, encuentre el estado después de ~T~ generaciones.

Input specification

La primera línea contiene dos enteros separados por un simple espacio ~N~ y ~T~ ~(3 \leq N \leq 100 000; 1 \leq T \leq 10^{15})~. La segunda línea contiene una cadena consistente de exactamente ~N~ caracteres representando la configuración inicial de las ~N~ celdas. Cada carácter en la cadena es \(‘0’ o ‘1’\). El estado inicial de la celda i está dado por el i-ésimo carácter de la cadena. El caracter \(‘1’\) representa una celda viva y el caracter \(‘0’\) representa una celda muerta.

Output specification

Imprima la cadena de ~N~ caracteres representando el estado final de las celdas en el mismo formato y orden de la entrada.

Sample input

7 1

0000001

Sample output

1000010

Hint(s)

Ejemplo 2 de entrada

5 3

01011

Ejemplo 2 de salida

10100

Explicación de ejemplo 1: La celda 1 y la celda ~N-1~ son adyacentes a la celda ~N~ así que viven después de una generación.

Explicación de ejemplo 2: Después de una generación la combinación es ~00011~. Después de dos generaciones es ~10111~.