M. Mondrialayag
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Bob is making yet another grid-based painting for his school's art exhibit. This year, he decided to take some inspiration from Alice and inject some fun mathematics into his construction this year!

A magic square is an $$$n \times n$$$ grid such that:

  • Each of its squares contains a distinct positive integer.
  • The sum of the entries along each row and column, as well as the sum of the entries along the main diagonal (top-left to bottom-right corners) and along the anti-diagonal (top-right to bottom-left corners) are all the same.
Here is one classic example of a $$$4 \times 4$$$ magic square, where the rows, columns, and diagonals sum up to $$$100$$$.
30161836
10442224
32142034
2826406
It turns out that finding magic squares is a bit hard for Bob, so Bob decided to invent Mondrialayagic squares, inspired by Froilan Calayag and the artist's surrealist art. An $$$n \times n$$$ Mondrialayagic square has the following properties.
  • Each of its squares contains a distinct positive integer from 1 to 101.
  • The sum of the entries along each row and column, as well as the sum of the entries along the main diagonal and along the anti-diagonal, are all the same modulo 101.
    • These sums do not necessarily have to all be exactly the same... they just need to all give the same remainder when divided by $$$101$$$.
Here is one example of a $$$4 \times 4$$$ Mondrialayagic square.
80557333
14826
98379115
62446966
Here, we see that:
  • The rows sum up to: $$$241$$$, $$$39$$$, $$$241$$$, and $$$241$$$ (from top to bottom).
  • The columns sum up to: $$$241$$$, $$$140$$$, $$$241$$$, and $$$140$$$ (from left to right).
  • The main diagonal sums up to $$$241$$$, and the anti-diagonal sums up to $$$140$$$.
Since all these values leave a remainder of $$$39$$$ when divided by $$$101$$$, we consider all of them to be equal modulo 101, and thus this is a Mondrialayagic square.

Bob will pre-fill in at most two values in an $$$n \times n$$$ grid, since those values at those position are very important for the message he wants to communicate with his art. Can you help him by constructing any Mondrialayagic square around them? That is, find any Mondrialayagic square that has those pre-filled values at those positions.

If none exist, you should say so as well.

Input

The first line of input contains a single integer $$$T$$$, denoting the number of test cases. The descriptions of $$$T$$$ test cases follow.

The first line of each test case contains a single integer $$$n$$$.

Then, $$$n$$$ lines follow, each containing a row of $$$n$$$ values.

  • If the value is ? then you may substitute it with anything.
  • If the value is a positive integer from $$$1$$$ to $$$101$$$, then this value must appear at this position.
Output

For each test case...

If the task is impossible, output a single line containing the word NO.

If the task is possible, first output a line containing the word YES, followed by your Mondrialayagic square.

This should be $$$n$$$ lines, each containing $$$n$$$ space-separated positive integers. This must be a valid Mondrialayagic square, and the values specified in the input must still be there at their same positions.

If there are multiple possible solutions, any will be accepted.

Scoring

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq T \leq 5000 \\ 3 \leq n \leq 6 \\ \text{The pre-filled squares contain distinct values from $1$ to $101$.} \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{23} & \text{There are no pre-filled squares.} \\ \hline 2 & \mathbf{33} & \text{There is at most one pre-filled square.} \\ \hline 3 & \mathbf{44} & \text{There are at most two pre-filled squares.} \\ \hline \end{array}\\

\end{align*}$$$$$$

Example
Input
1
4
? ? ? ?
1 ? ? ?
? ? ? ?
? ? 69 ?
Output
YES
80 55 73 33
1 4 8 26
98 37 91 15
62 44 69 66