If you follow the news on social media, you have surely already heard several different conspiracy theories about various secret organizations with plans for vaccinating people, poisoning body fluids with fluorine, etc. A young man named Martin has recently been secured a job as the director of a well-known Croatian newspaper by one such organization.

The organization did not take an interest in the newspaper without a reason. Namely, they need a way to slowly and inefficiently send messages to all their members while creating as many conspiracy theories as possible. Due to certain numerical-mystical properties, the organization instructed Martin to use an unusual medium for sending messages. Instead of hiding messages in the texts of articles, he must hide them in the puzzle section of the newspaper. More precisely, in Sudoku puzzles.

A Sudoku puzzle is a $9 \times 9$ grid in which some fields are filled with numbers from one to nine. The puzzle is divided into 9 rows, 9 columns, and 9 square blocks of size $3 \times 3$. A puzzle is considered solved when all fields are filled with numbers from one to nine such that the numbers do not repeat in any row, column, or block.

Martin's task is to write a program that will encode a sequence of $N$ words $s_i$ into $N$ Sudoku puzzles and then decode those puzzles back into words.

The newspaper's puzzle makers will not allow Martin to put just any Sudoku puzzle in the newspaper; they will create the puzzle by removing a certain number of numbers from the solved puzzle that Martin proposes, depending on the required difficulty. Therefore, Martin's program must encode words into solved Sudoku puzzles.

Martin's superiors believe that every member of the organization should be able to solve such a puzzle, so the decoding part of the program must only decode fully filled puzzles.

Programming is not Martin's strong suit, so he asks you to write such a program.

Input

The first line contains the natural numbers $M$ and $N$ ($M = 1$ or $M = 2$, $1 \le N \le 30$). If $M = 1$, the program should encode $N$ strings into Sudoku puzzles, and if $M = 2$, the program must decode $N$ Sudoku puzzles back into strings.

If $M = 1$, the $i$-th of the following $N$ lines contains a natural number $l_i$ and a string $s_i$ ($1 \le |s_i| = l_i \le 15$). The strings $s_i$ consist exclusively of lowercase English letters.

If $M = 2$, the following $9N$ lines contain $N$ matrices of format $9 \times 9$ which represent the Sudoku puzzles that need to be decoded. The matrices will always form valid puzzles, meaning they will consist of characters $1-9$ and no number will repeat in a $3 \times 3$ block, row, or column of the matrix.

Output

If $M = 1$, print $N$ Sudoku puzzles in $9N$ lines that represent the encoded values of the strings $s_i$ from the input. The printed puzzles must consist exclusively of characters $1-9$, and the numbers in rows, columns, and $3 \times 3$ blocks must not repeat.

If $M = 2$, print the decoded strings of the Sudoku puzzles from the input in $N$ lines.

Subtasks

Examples

Input 1

1 1
6 sudoku

Output 1

139245678
628137459
457689123
214356897
375498216
896712345
541873962
763921584
982564731

Input 2

2 1
139245678
628137459
457689123
214356897
375498216
896712345
541873962
763921584
982564731

Output 2

sudoku