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 (N2 × N2) 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 N2 × N2 sudoku.
Input
The first line of input contains a single integer, N.
Each of the following N2 lines contains N2 space-separated values, ranging from 0 to N2.
A value of 0 denotes an empty cell.
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, 16×16 and 25×25 sudokus (in this order), and are slightly easier to solve than the ones used in the final tests.
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 |
