Mooyo Mooyo#10398

Mooyo Mooyo

1 segundo

128 megabytes

Fácil

Con mucho tiempo libre entre manos (o más bien, entre pezuñas), las vacas de la granja de Farmer John suelen pasar el tiempo jugando videojuegos. Uno de sus favoritos está basado en un popular videojuego humano llamado Puyo Puyo; la versión vacuna, por supuesto, se llama Mooyo Mooyo.

Mooyo Mooyo se juega en una cuadrícula alta y angosta que tiene $n$ celdas de alto y $10$ celdas de ancho. Aquí hay un ejemplo con $n = 6$ n = 6:

Cada celda está vacía (denotada por $0$ ) o contiene una pacas de heno de uno de nueve colores (denotados por los dígitos del $1$ al $9$ ). La gravedad hace que las pacas de heno caigan hacia abajo, por lo que nunca hay una celda vacía debajo de una paca de heno.

Dos celdas pertenecen a la misma región conectada si son adyacentes horizontal o verticalmente y tienen el mismo color distinto de cero. Cada vez que existe una región conectada de al menos $k$ celdas, todas sus pacas de heno desaparecen y las celdas quedan vacías. Si existen varias regiones de este tipo al mismo tiempo, todas desaparecen simultáneamente. Después de eso, la gravedad puede hacer que las pacas de heno caigan en algunas de las celdas recién vaciadas. La configuración resultante puede nuevamente contener regiones conectadas de al menos $k$ celdas. Si es así, también desaparecen (simultáneamente, si hay varias), la gravedad nuevamente atrae hacia abajo las pacas de heno restantes, y el proceso se repite hasta que no quede ninguna región conectada de al menos $k$ celdas.

Dado el estado inicial de un tablero de Mooyo Mooyo, imprime el estado final del tablero después de todas estas operaciones.

Entrada

La primera línea contiene dos números enteros $n$ y $k (1 \leq n \leq 100, 1 \leq k \leq 10 n)$ k~(1 \le n \le 100, 1 \le k \le 10n). Cada una de las siguientes $n$ líneas contiene $10$ dígitos y describe una fila del tablero inicial.

Salida

Imprime $n$ líneas que describen el estado final del tablero en el mismo formato.

Ejemplos

En el ejemplo anterior, si $k = 3$ k = 3, hay una región conectada de al menos $k$ celdas de color $1$ y otra de color $2$ . Después de que se eliminan simultáneamente, el tablero se ve temporalmente así:

Luego la gravedad entra en acción, y las pacas de heno caen en la siguiente configuración:

Nuevamente, hay una región de al menos $k$ celdas (de color $3$ ). Al eliminarla se obtiene la configuración final del tablero:

Ejemplo 1