Jeśli śledzicie wiadomości w mediach społecznościowych, z pewnością słyszeliście już kilka różnych teorii spiskowych o rozmaitych tajnych organizacjach, które planują wszczepianie ludziom chipów za pomocą szczepionek, zatruwanie płynów ustrojowych fluorem i tym podobne rzeczy. Właśnie jedna z takich organizacji zapewniła niedawno młodemu Martinowi posadę dyrektora znanej chorwackiej gazety.

Organizacja zainteresowała się gazetą nie bez powodu. Potrzebuje bowiem sposobu na powolne i nieefektywne wysyłanie wiadomości wszystkim swoim członkom, a przy tym tworzenie jak największej liczby teorii spiskowych. Ze względu na pewne właściwości numeryczno-mistyczne organizacja poleciła Martinowi używać do przesyłania wiadomości niezwykłego medium. Zamiast ukrywać wiadomości w tekstach artykułów, musi je ukrywać w dziale łamigłówek gazety. Dokładniej, w sudoku.

Sudoku to plansza złożona z $9 \times 9$ pól, w niektórych z nich wpisano liczby od jednego do dziewięciu. Plansza jest podzielona na 9 wierszy, 9 kolumn i 9 kwadratowych bloków o rozmiarze $3 \times 3$. Sudoku uważa się za rozwiązane, gdy wszystkie pola są wypełnione liczbami od jednego do dziewięciu tak, aby w żadnym wierszu, kolumnie ani bloku liczby się nie powtarzały.

Zadaniem Martina jest napisanie programu, który zakoduje ciąg $N$ słów $s_i$ w $N$ planszach sudoku, a następnie odkoduje te plansze z powrotem na słowa.

Autorzy łamigłówek w gazecie nie pozwolą Martinowi umieścić w niej dowolnego sudoku. Przygotują łamigłówkę, usuwając pewną liczbę cyfr z rozwiązanej planszy zaproponowanej przez Martina, zależnie od wymaganego poziomu trudności. Program Martina musi więc kodować słowa w rozwiązanych planszach sudoku.

Przełożeni Martina wierzą, że każdy członek organizacji powinien umieć rozwiązać taką łamigłówkę, więc część programu służąca do odkodowywania musi odkodowywać jedynie wypełnione plansze.

Programowanie nie jest mocną stroną Martina, dlatego prosi was o napisanie takiego programu.

Wejście

W pierwszym wierszu znajdują się dodatnie liczby całkowite $M$ i $N$ ($M = 1$ lub $M = 2$, $1 \le N \le 30$). Jeśli $M = 1$, program powinien zakodować $N$ napisów w planszach sudoku, a jeśli $M = 2$, musi odkodować $N$ plansz sudoku z powrotem na napisy.

Jeśli $M = 1$, w $i$-tym z następnych $N$ wierszy znajdują się dodatnia liczba całkowita $l_i$ oraz napis $s_i$ ($1 \le |s_i| = l_i \le 15$). Napisy $s_i$ składają się wyłącznie z małych liter alfabetu angielskiego.

Jeśli $M = 2$, w następnych $9N$ wierszach znajduje się $N$ macierzy o rozmiarze $9 \times 9$, reprezentujących plansze sudoku, które należy odkodować. Macierze zawsze będą poprawnymi rozwiązaniami sudoku: będą składać się ze znaków 1–9, a żadna liczba nie będzie powtarzać się w bloku $3 \times 3$, wierszu ani kolumnie macierzy.

Wyjście

Jeśli $M = 1$, wypisz w $9N$ wierszach $N$ plansz sudoku reprezentujących zakodowane wartości napisów $s_i$ z wejścia. Wypisane plansze mogą składać się wyłącznie ze znaków 1–9, a liczby w wierszach, kolumnach i blokach $3 \times 3$ nie mogą się powtarzać.

Jeśli $M = 2$, wypisz w $N$ wierszach napisy odkodowane z plansz sudoku podanych na wejściu.

Podzadania

Wasze rozwiązanie będzie testowane w dwóch etapach. Najpierw zostanie uruchomione z oficjalnymi danymi wejściowymi, w których $M = 1$. Jeśli wynikiem działania rozwiązania będzie ciąg $N$ poprawnych macierzy, w drugim etapie rozwiązanie zostanie uruchomione ponownie z macierzami wypisanymi w pierwszym etapie. Jeśli napisy wypisane przez program w drugim etapie będą takie same jak napisy w oficjalnych danych wejściowych, otrzymacie wszystkie punkty za ten test.

Czas działania rozwiązania jest sumą czasów działania obu etapów oceniania.

Przykład

Wejście 1

1 1
6 sudoku

Wyjście 1

139245678
628137459
457689123
214356897
375498216
896712345
541873962
763921584
982564731

Wejście 2

2 1
139245678
628137459
457689123
214356897
375498216
896712345
541873962
763921584
982564731

Wyjście 2

sudoku