A Sudoku puzzle generally consists of $n$ blocks of size $\sqrt{n} \times \sqrt{n}$ in an $n \times n$ grid.

Each row and each column must contain the numbers $1 \sim n$, with no omissions and no repetitions. Each block (the region enclosed by thick black lines, typically $\sqrt{n} \times \sqrt{n}$) must also contain the numbers $1 \sim n$, with no omissions and no repetitions. A completed puzzle must satisfy all three conditions simultaneously.

The figure above shows an example of an $n \times n$ Sudoku puzzle ($n=9$).

Given an incomplete Sudoku puzzle, you are required to fill in any number of cells such that the completed Sudoku has exactly two solutions. Among all such ways to complete the puzzle, you must choose one where the difference between the two solutions is maximized. Here, the difference is defined as the number of cells where the two solutions contain different digits.

Additionally, for any two positions in the Sudoku, let $x_1, x_2$ be the digits in the two solutions at the first position, and $y_1, y_2$ be the digits in the two solutions at the second position. It is not the case that $x_1 \neq x_2, y_1 \neq y_2, x_1 \neq y_2,$ and $x_1 \neq y_1$ are all satisfied simultaneously.

Input

The first line contains an integer $n$, representing the size of the Sudoku.

The next $n$ lines each contain $n$ integers $a_{i,j}$, representing an incomplete Sudoku puzzle. A value of $0$ indicates an empty cell.

Output

Output $n$ lines, each containing $n$ integers, representing the completed grid. If there are multiple ways to complete the puzzle that satisfy the condition of having exactly two solutions with the maximum possible difference, you may output any one of them.

Examples

Input 1

4
3 0 0 0
0 0 0 0
0 3 0 0
0 0 0 3

Output 1

3 0 0 0
0 0 0 2
0 3 0 0
2 0 0 3

Note

The two solutions corresponding to the sample output are:

3 2 1 4
1 4 3 2
4 3 2 1
2 1 4 3

and:

3 2 4 1
4 1 3 2
1 3 2 4
2 4 1 3

Comparing them cell by cell, the difference is $8$. It can be proven that this is one of the ways to achieve the maximum difference of $8$ for this puzzle.

Data Range

For all data: $a_{i,j} \in [0, n]$. It is guaranteed that the given incomplete Sudoku puzzle has at least one completion that results in exactly two solutions.

Test Case 14

16
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Test Case 15

16
0 0 10 0 0 0 0 1 0 0 0 0 0 0 0 16
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 16 0 0 0 0 0 0 0 0 0 0 2 0 0
0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0
0 0 0 0 9 0 0 0 0 0 0 0 0 7 0 0
7 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 15 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 7 0 0 0 0 0 0 0 0 0 0 0 9 0
0 0 0 0 8 0 0 0 0 0 0 0 0 0 0 0
13 0 0 0 0 0 0 0 0 0 8 0 0 0 12 11