Complete the Sudoku Grid

In this problem, you are given an incomplete Sudoku grid of size (n\times n), where (n) is a perfect square (for example, 4 or 9). Each row, column, and each (\sqrt{n}\times\sqrt{n}) sub-grid must contain all the integers from 1 to (n) exactly once. Blank cells are denoted by 0. Your task is to fill in the empty cells so that the final grid satisfies the Sudoku rules.

The rules can be formally described as follows:

1. Every row must contain each number from 1 to (n) exactly once: (\forall, r, ; {grid[r][c] : 0 \le c < n} = {1,2,\dots,n}).
2. Every column must contain each number from 1 to (n) exactly once: (\forall, c, ; {grid[r][c] : 0 \le r < n} = {1,2,\dots,n}).
3. Every sub-grid of size (\sqrt{n}\times\sqrt{n}) must contain each number from 1 to (n) exactly once.

You must read from the standard input and write the completed grid to standard output. The completed grid must replace all 0s with appropriate numbers satisfying the constraints. If the grid is already valid and complete, output it as is.

It is guaranteed that if the grid has a solution, it is unique for the test cases provided.

inputFormat

The input is given via standard input. The first line contains an integer (n), representing the number of rows (and columns) in the grid. The following (n) lines each contain (n) space-separated integers representing the rows of the Sudoku grid. Empty cells are marked with 0.

outputFormat

Output the completed Sudoku grid to standard output. The grid should be printed in (n) lines, each with (n) space-separated integers. There should be no extra spaces or blank lines.## sample

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

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