Isobel is passionate about Logic and finds **Sudoku** to be a particularly interesting puzzle. During the discussions with other people who share the same passion for this game, she found out that solving a general sudoku (** N^{2} × N^{2}**) is a hard task and no polynomial solution is known. It can be reduced to graph vertex colouring, which is well known to be a very difficult problem.

Isobel has already solved so many **Sudoku** puzzles that she got bored and now wants to find out if you can write a program which can solve an ** N^{2} × N^{2}** sudoku.

### Input

The first line of input contains a single integer, ** N**.

Each of the following

**lines contains**

`N`^{2}**space-separated values, ranging from**

`N`^{2}**to**

`0`**.**

`N`^{2}A value of

**denotes an empty cell.**

`0`### Output

The output should contain a complete solution to the given sudoku, in the same format.

### Constraints

`1 ≤ N ≤ 5`- It is guaranteed that there exists a
**unique solution**. - The three pretests contain
,`9×9`and`16×16`sudokus (in this order), and are slightly easier to solve than the ones used in the final tests.`25×25`

### Sample

Input | Output |
---|---|

3 0 0 0 0 4 0 0 0 0 0 0 2 6 0 7 1 0 0 8 7 1 0 0 0 6 9 4 0 6 0 0 0 0 0 4 0 2 0 5 9 0 6 7 0 8 0 8 0 0 0 0 0 2 0 6 5 8 0 0 0 4 7 1 0 0 9 4 0 8 5 0 0 0 0 0 0 7 0 0 0 0 | 5 3 6 1 4 9 2 8 7 4 9 2 6 8 7 1 5 3 8 7 1 3 2 5 6 9 4 9 6 7 8 1 2 3 4 5 2 4 5 9 3 6 7 1 8 1 8 3 7 5 4 9 2 6 6 5 8 2 9 3 4 7 1 7 1 9 4 6 8 5 3 2 3 2 4 5 7 1 8 6 9 |