Description

Given positive integers $n, m, k$, is it possible to color an $n \times m$ grid such that each color forms exactly one connected component, and every connected component has size $k$?

If it is possible, construct a valid solution.

Input Format

This problem contains multiple test cases.

The first line contains a positive integer $T$, indicating the number of test cases.

The next $T$ lines each contain three positive integers $n, m, k$.

Output Format

Output $T$ lines. The $i$-th line contains the answer for the $i$-th test case. If it is possible, output YES; otherwise, output NO.

If it is possible, then output $n$ more lines, each containing $m$ positive integers. Each integer must be no greater than $10^9$, and cells with the same integer must form a connected component of size exactly $k$.

3
3 3 3
3 3 33
6 6 4

YES
1 1 2
1 2 2
3 3 3
NO
YES
1 1 2 2 3 3
1 2 2 4 4 3
1 5 5 4 6 3
5 5 7 4 6 6
8 7 7 7 9 6
8 8 8 9 9 9

Hint

Explanation for Sample 1

One possible valid output for test case 3:

Constraints

This problem uses bundled tests.

• Subtask 1 (20 pts): $k = 1$.
• Subtask 2 (30 pts): $n = 1$.
• Subtask 3 (50 pts): no special restrictions.

For $100\%$ of the testdata, $1 \le n, m, k, T, \sum nm \le 10^{6}$.

Translated by ChatGPT 5