Un texto binario es bacán si no tiene \(K\) o más caracteres iguales seguidos. Se da un texto binario \(S\); en cada operación se elige una posición y se invierte su carácter (0 ↔ 1). Transforma \(S\) en un texto bacán con la mínima cantidad de operaciones.

Entrada

Una línea con un entero \(K\) y un texto binario \(S\) \((2 \le K \le |S| \le 10^5)\).

Salida

Una línea con la mínima cantidad de operaciones seguida de un texto bacán que se obtiene de \(S\) con esa cantidad de operaciones. Si hay varios, cualquiera es aceptado.

Ejemplo 1

Entrada

2 00

Salida

1 01

Ejemplo 2

Entrada

2 10

Salida

0 10

Ejemplo 3

Entrada

3 1111100

Salida

1 1101100

Ejemplo 4

Entrada

3 00001111

Salida

2 01001101

Regional Latinoamericana 2024 del ICPC, problema K («Kool Strings»). Versión en español redactada para este juez; el enunciado oficial, en inglés, está aquí abajo.