Wenn du die Nachrichten in sozialen Netzwerken verfolgst, hast du sicher schon einige verschiedene Verschwörungstheorien über geheime Organisationen gehört, die planen, Menschen durch Impfstoffe zu chippen, Körperflüssigkeiten mit Fluor zu vergiften und Ähnliches. Genau eine solche Organisation hat dem jungen Martin kürzlich eine Stelle als Direktor einer bekannten kroatischen Zeitung verschafft.

Die Organisation interessiert sich nicht ohne Grund für die Zeitung. Sie benötigt nämlich eine Möglichkeit, langsam und ineffizient Nachrichten an alle ihre Mitglieder zu senden und dabei möglichst viele Verschwörungstheorien hervorzurufen. Aufgrund bestimmter numerisch-mystischer Eigenschaften hat die Organisation Martin angewiesen, ein ungewöhnliches Medium für die Nachrichten zu nutzen. Statt sie in den Texten der Artikel zu verstecken, muss er sie im Rätselteil der Zeitung verstecken. Genauer gesagt: in Sudoku-Rätseln.

Ein Sudoku-Rätsel ist eine Matrix mit $9\times9$ Feldern, von denen einige mit Zahlen von eins bis neun gefüllt sind. Das Rätsel ist in $9$ Zeilen, $9$ Spalten und $9$ quadratische Blöcke der Größe $3\times3$ unterteilt. Es gilt als gelöst, wenn alle Felder mit Zahlen von eins bis neun gefüllt sind, sodass sich in keiner Zeile, Spalte oder keinem Block Zahlen wiederholen.

Martins Aufgabe ist es, ein Programm zu schreiben, das eine Folge von $N$ Wörtern $s_i$ in $N$ Sudoku-Rätsel kodiert und diese Rätsel anschließend wieder in Wörter dekodiert.

Die Rätselredakteure der Zeitung werden Martin nicht erlauben, beliebige Sudoku-Rätsel in die Zeitung zu setzen. Stattdessen werden sie abhängig vom gewünschten Schwierigkeitsgrad eine bestimmte Anzahl von Zahlen aus dem gelösten Rätsel entfernen, das Martin vorschlägt. Martins Programm muss die Wörter also in gelöste Sudoku-Rätsel kodieren.

Martins Vorgesetzte glauben, dass jedes Mitglied der Organisation ein solches Rätsel lösen können sollte. Daher muss auch der dekodierende Teil des Programms nur vollständig ausgefüllte Rätsel dekodieren.

Programmieren ist nicht Martins Stärke, deshalb bittet er dich, ein solches Programm zu schreiben.

Eingabe

Die erste Zeile enthält die natürlichen Zahlen $M$ und $N$ ($M=1$ oder $M=2$, $1\le N\le30$). Wenn $M=1$ ist, soll das Programm $N$ Zeichenketten in Sudoku-Rätsel kodieren. Wenn $M=2$ ist, muss es $N$ Sudoku-Rätsel wieder in Zeichenketten dekodieren.

Wenn $M=1$ ist, enthält die $i$-te der folgenden $N$ Zeilen jeweils eine natürliche Zahl $l_i$ und eine Zeichenkette $s_i$ ($1\le |s_i|=l_i\le15$). Die Zeichenketten $s_i$ bestehen ausschließlich aus Kleinbuchstaben des englischen Alphabets.

Wenn $M=2$ ist, enthalten die folgenden $9N$ Zeilen $N$ Matrizen der Größe $9\times9$, welche die zu dekodierenden Sudoku-Rätsel darstellen. Die Matrizen bilden stets gültige Rätsel: Sie bestehen aus den Zeichen 1 bis 9, und keine Zahl wiederholt sich in einem $3\times3$-Block, einer Zeile oder einer Spalte der Matrix.

Ausgabe

Wenn $M=1$ ist, gib in $9N$ Zeilen $N$ Sudoku-Rätsel aus, welche die kodierten Werte der Eingabezeichenketten $s_i$ darstellen. Die ausgegebenen Rätsel dürfen ausschließlich aus den Zeichen 1 bis 9 bestehen, und in den Zeilen, Spalten und $3\times3$-Blöcken dürfen sich keine Zahlen wiederholen.

Wenn $M=2$ ist, gib in $N$ Zeilen die dekodierten Zeichenketten der Sudoku-Rätsel aus der Eingabe aus.

Teilaufgaben

Deine Lösung wird in zwei Schritten getestet. Zuerst wird sie mit den offiziellen Eingabedaten aufgerufen, in denen $M=1$ gilt. Wenn die Ausgabe deiner Lösung eine Folge von $N$ gültigen Matrizen ist, wird deine Lösung im zweiten Schritt mit den im ersten Schritt ausgegebenen Matrizen erneut gestartet. Wenn die Zeichenketten, die dein Programm im zweiten Schritt ausgibt, mit den Zeichenketten der offiziellen Eingabedaten übereinstimmen, erhältst du alle Punkte für diese offizielle Eingabe.

Die Laufzeit deiner Lösung ist die Summe der Laufzeiten beider Bewertungsschritte.

Beispiele

Eingabe 1

1 1
6 sudoku

Ausgabe 1

139245678
628137459
457689123
214356897
375498216
896712345
541873962
763921584
982564731

Eingabe 2

2 1
139245678
628137459
457689123
214356897
375498216
896712345
541873962
763921584
982564731

Ausgabe 2

sudoku