P7886 "MCOI-06" Gerrymandering

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.

**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 $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$.

#### 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