Problem Description

We define an $n \times n$ matrix $A$ to be a Latin square if and only if each row and each column is a permutation of $1 \sim n$.

Now you are given an $R \times C$ submatrix in the top-left corner of matrix $A$, i.e., the entries $A_{i, j}$ ($1 \le i \le R$, $1 \le j \le C$). Determine whether it is possible to fill the remaining entries so that the whole matrix becomes a Latin square.

Input Format

Multiple test cases. The first line contains an integer $T$, the number of test cases.
For each test case, the first line contains three integers $n, R, C$, representing the matrix size and the size of the known submatrix.
Then follow $R$ lines, each containing $C$ numbers. The $j$-th number in the $i$-th line represents $A_{i, j}$.

Output Format

For each test case, output a string Yes or No in the first line, indicating whether a Latin square satisfying the conditions can be found.
If it can be found, then output $n$ more lines, each containing $n$ numbers, representing one valid Latin square. If multiple valid solutions exist, output any one of them.

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

Yes
1 2
2 1
No
Yes
1 2 3 4 5
4 3 2 5 1
2 4 5 1 3
3 5 1 2 4
5 1 4 3 2

Hint

[Sample #1 Explanation]

In the first sample, for the second test case, from the first two rows we can see that $A_{1, 3} = A_{2, 3} = 3$, so no Latin square satisfying the conditions exists.

For the third test case, we can see that the output is a valid Latin square, and its top-left corner matches the input matrix. The following is also a valid solution.

$$\begin{bmatrix} 1 & 2 & 3 & 5 & 4 \\ 4 & 3 & 2 & 1 & 5 \\ 3 & 5 & 1 & 4 & 2 \\ 2 & 4 & 5 & 3 & 1 \\ 5 & 1 & 4 & 2 & 3 \end{bmatrix}$$

---

[Sample #2]

See the attachments latin/latin2.in and latin/latin2.ans. This sample satisfies the constraint limits of test points $6 \sim 7$.

---

[Sample #3]

See the attachments latin/latin3.in and latin/latin3.ans. This sample satisfies the constraint limits of test points $11 \sim 12$.

---

[Constraints]

For all testdata, it is guaranteed that $1 \le T \le 10$, $1 \le n \le 500$, $1 \le R, C \le n$, $1 \le A_{i, j} \le n$. It is guaranteed that in the input submatrix, no row or column contains two identical numbers.

Details are as follows:

Test Point ID	$n \le$	Special Property
$1 \sim 2$	$6$	None
$3 \sim 4$	$10$
$5$	$500$	A
$6 \sim 7$	$100$	B
$8 \sim 9$	$300$
$10$	$500$
$11 \sim 12$		C
$13 \sim 14$	$100$	None
$15 \sim 16$	$300$
$17 \sim 20$	$500$

Special property A: It is guaranteed that $R = 1$.
Special property B: It is guaranteed that $C = n$.
Special property C: It is guaranteed that $R, C \le \frac{n}{2}$.

Translated by ChatGPT 5