Si vous suivez l'actualité sur les réseaux sociaux, vous avez sûrement déjà entendu plusieurs théories du complot concernant diverses organisations secrètes qui prévoient d'implanter des puces chez les gens au moyen de vaccins, d'empoisonner les fluides corporels avec du fluor, etc. Une telle organisation vient justement de procurer au jeune Martin un poste de directeur d'un célèbre journal croate.

Ce n'est pas sans raison que l'organisation s'est intéressée au journal. Elle a en effet besoin d'un moyen d'envoyer lentement et inefficacement des messages à tous ses membres, tout en suscitant le plus grand nombre possible de théories du complot. En raison de certaines propriétés numérico-mystiques, l'organisation a ordonné à Martin d'utiliser un support inhabituel pour envoyer ses messages. Au lieu de les cacher dans le texte des articles, il doit les dissimuler dans la rubrique de jeux du journal. Plus précisément, dans les grilles de sudoku.

Une grille de sudoku est une matrice de $9 \times 9$ cases dont certaines contiennent des nombres de un à neuf. Elle est divisée en $9$ lignes, $9$ colonnes et $9$ blocs carrés de taille $3 \times 3$. Elle est considérée comme résolue lorsque toutes les cases contiennent des nombres de un à neuf, sans qu'aucun nombre se répète dans une ligne, une colonne ou un bloc.

Martin doit écrire un programme qui encode une suite de $N$ mots $s_i$ dans $N$ grilles de sudoku, puis décode ces grilles pour retrouver les mots.

Les concepteurs de jeux du journal ne laisseront pas Martin y publier n'importe quelle grille de sudoku. Ils créeront plutôt la grille en retirant un certain nombre de nombres de la grille résolue proposée par Martin, selon la difficulté souhaitée. Le programme de Martin doit donc encoder les mots dans des grilles de sudoku résolues.

Les supérieurs de Martin pensent que chaque membre de l'organisation devrait pouvoir résoudre une telle grille. La partie du programme chargée du décodage ne doit donc décoder que des grilles entièrement remplies.

La programmation n'est pas le point fort de Martin, et il vous demande d'écrire un tel programme.

Entrée

La première ligne contient les entiers naturels $M$ et $N$ ($M = 1$ ou $M = 2$, $1 \le N \le 30$). Si $M = 1$, le programme doit encoder $N$ chaînes en grilles de sudoku ; si $M = 2$, il doit décoder $N$ grilles de sudoku pour retrouver les chaînes.

Si $M = 1$, la $i$-ème des $N$ lignes suivantes contient un entier naturel $l_i$ et une chaîne $s_i$ ($1 \le |s_i| = l_i \le 15$). Les chaînes $s_i$ sont composées uniquement de lettres minuscules de l'alphabet anglais.

Si $M = 2$, les $9N$ lignes suivantes contiennent $N$ matrices de taille $9 \times 9$ représentant les grilles de sudoku à décoder. Les matrices formeront toujours des grilles valides : elles seront composées des caractères 1 à 9, et aucun nombre ne se répétera dans un bloc $3 \times 3$, une ligne ou une colonne de la matrice.

Sortie

Si $M = 1$, affichez sur $9N$ lignes $N$ grilles de sudoku représentant les valeurs encodées des chaînes $s_i$ de l'entrée. Les grilles affichées ne doivent contenir que les caractères 1 à 9, et les nombres ne doivent pas se répéter dans les lignes, les colonnes ou les blocs $3 \times 3$.

Si $M = 2$, affichez sur $N$ lignes les chaînes décodées des grilles de sudoku de l'entrée.

Sous-tâches

Votre solution sera testée en deux étapes. Elle sera d'abord exécutée avec les données d'entrée officielles dans lesquelles $M = 1$. Si elle produit une suite de $N$ matrices valides, elle sera exécutée une seconde fois avec les matrices produites à la première étape. Si les chaînes affichées par votre programme à la deuxième étape sont identiques aux chaînes des données d'entrée officielles, vous obtiendrez tous les points pour cette entrée officielle.

Le temps d'exécution de votre solution est la somme des temps d'exécution des deux étapes de l'évaluation.

Exemples

Entrée 1

1 1
6 sudoku

Sortie 1

139245678
628137459
457689123
214356897
375498216
896712345
541873962
763921584
982564731

Entrée 2

2 1
139245678
628137459
457689123
214356897
375498216
896712345
541873962
763921584
982564731

Sortie 2

sudoku