Fiendish Sudoku

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

InputOutput
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
Questions?

Sponsors Gold