Sudoku 3

Fereydun, the legendary Persian hero whose prophecy was to overcome Zahhak, believes that he needs a powerful mind together with a powerful body. He has just learned a new brain teaser called Sudoku from a Japanese trader. Sudoku is played on a board that is a grid of $n^2 \times n^2$ cells. The whole grid is also partitioned into $n^2$ sub-grids, each of size $n \times n$. Each cell can be empty or contain an integer from $1$ to $n^2$ (inclusive). A Sudoku board is valid if it meets the following conditions: 1. All numbers in each row are distinct. 2. All numbers in each column are distinct. 3. All numbers in each sub-grid are distinct. The following figure shows two valid Sudoku boards with no empty cells: Fereydun has a valid board with some empty cells and has asked for your help. Fill as many empty cells as you can while keeping the board valid. It is guaranteed that at least one way exists to fill all the empty cells while keeping the board valid. This is an output-only problem, so no source code submission is required. There are $10$ test cases. For each test case, you are given an input file containing a table $A$ as the initial state of a Sudoku board. Submit an output file containing a table $B$ as the final state of that board after filling some of its empty cells. All $A[i][j]$ and $B[i][j]$ values (for $1 \le i,j \le n^2$) are integers from $0$ to $n^2$ (inclusive), where $0$ marks an empty cell.

The first line contains $n$. Line $1+i$ (for $1 \le i \le n^2$) contains $A[i][1]$, $A[i][2]$, ..., $A[i][n^2]$, separated by spaces.

Line $i$ (for $1 \le i \le n^2$) must contain $B[i][1]$, $B[i][2]$, ..., $B[i][n^2]$, separated by spaces.

$2 \le n \le 20$. $0 \le A[i][j] \le n^2$. The board $A$ is valid, and all of its empty cells can be filled while keeping it valid.