Si sigues las noticias en las redes sociales, seguramente ya habrás oído varias teorías de conspiración sobre distintas organizaciones secretas que planean implantar chips en las personas mediante vacunas, envenenar los fluidos corporales con flúor y cosas similares. Precisamente una de esas organizaciones acaba de conseguirle al joven Martin un empleo como director de un conocido periódico croata.

La organización no se interesó por el periódico sin motivo. Necesita una forma de enviar mensajes lenta e ineficazmente a todos sus miembros y, al mismo tiempo, generar tantas teorías de conspiración como sea posible. Debido a ciertas propiedades numéricas y místicas, la organización le ha ordenado a Martin que utilice un medio inusual para enviar los mensajes. En lugar de esconderlos en los textos de los artículos, debe esconderlos en la sección de pasatiempos del periódico. Más concretamente, en los sudokus.

Un sudoku es una matriz de $9 \times 9$ casillas, algunas de las cuales contienen números del uno al nueve. El sudoku se divide en 9 filas, 9 columnas y 9 bloques cuadrados de tamaño $3 \times 3$. Se considera resuelto cuando todas sus casillas contienen números del uno al nueve y ningún número se repite en una misma fila, columna o bloque.

La tarea de Martin es escribir un programa que codifique una secuencia de $N$ palabras $s_i$ en $N$ sudokus y que después decodifique esos sudokus para recuperar las palabras.

Los creadores de pasatiempos del periódico no permitirán que Martin publique cualquier sudoku. Para obtener la dificultad necesaria, prepararán el sudoku eliminando cierta cantidad de números del sudoku resuelto que Martin proponga. Por tanto, el programa de Martin debe codificar las palabras en sudokus resueltos.

Los superiores de Martin creen que cualquier miembro de la organización debería ser capaz de resolver un sudoku así, por lo que la parte del programa encargada de decodificar solo tiene que decodificar sudokus completos.

La programación no es el punto fuerte de Martin, así que te pide que escribas ese programa.

Entrada

La primera línea contiene los enteros positivos $M$ y $N$ ($M = 1$ o $M = 2$, $1 \le N \le 30$). Si $M = 1$, el programa debe codificar $N$ cadenas en sudokus; si $M = 2$, debe decodificar $N$ sudokus para recuperar las cadenas.

Si $M = 1$, la $i$-ésima de las siguientes $N$ líneas contiene un entero positivo $l_i$ y una cadena $s_i$ ($1 \le |s_i| = l_i \le 15$). Las cadenas $s_i$ contienen exclusivamente letras minúsculas del alfabeto inglés.

Si $M = 2$, las siguientes $9N$ líneas contienen $N$ matrices de tamaño $9 \times 9$ que representan los sudokus que se deben decodificar. Las matrices siempre serán sudokus válidos: contendrán caracteres del 1 al 9 y ningún número se repetirá en un bloque de $3 \times 3$, ni en una fila o columna de la matriz.

Salida

Si $M = 1$, imprime en $9N$ líneas $N$ sudokus que representen los valores codificados de las cadenas $s_i$ de la entrada. Los sudokus impresos solo pueden contener caracteres del 1 al 9, y los números no deben repetirse en las filas, columnas ni bloques de $3 \times 3$.

Si $M = 2$, imprime en $N$ líneas las cadenas decodificadas de los sudokus de la entrada.

Subtareas

Tu solución se probará en dos pasos. Primero se ejecutará con los datos de entrada oficiales, en los que $M = 1$. Si la salida de tu solución es una secuencia de $N$ matrices válidas, en el segundo paso se volverá a ejecutar tu solución con las matrices impresas en el primer paso. Si las cadenas que imprime tu programa en el segundo paso son iguales a las cadenas de los datos de entrada oficiales, obtendrás todos los puntos correspondientes a esa entrada oficial.

El tiempo de ejecución de tu solución es la suma de los tiempos de ejecución de los dos pasos de evaluación.

Ejemplos

Entrada 1

1 1
6 sudoku

Salida 1

139245678
628137459
457689123
214356897
375498216
896712345
541873962
763921584
982564731

Entrada 2

2 1
139245678
628137459
457689123
214356897
375498216
896712345
541873962
763921584
982564731

Salida 2

sudoku