K - (mod HW+1) Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 101 点

問題文

整数 H, W, R が与えられます。

H 行 W 列のマス目があり、あなたはすべてのマスに整数を 1 つずつ書き込もうとしています。

上から i 行目、左から j 列目に書き込む整数を P_{i, j} とおくとき、 以下の条件を満たす書き込み方が存在するか判定してください。 もし存在する場合には、そのような書き込み方の一例を求めてください。

  • (P_{1,1}, P_{1,2}, \ldots, P_{1, W}, P_{2, 1}, \ldots, P_{H, W}) は (1, 2, \ldots, H \times W) の並び替えである。

  • どの 2 \times 2 マスを選んでも、その中にある 4 つの整数の積を HW + 1 で割った余りが R に等しい。

    • より正確には、任意の 1 \leq i \leq H-1, 1 \leq j \leq W-1 に対し、 P_{i, j} \times P_{i+1, j} \times P_{i, j+1} \times P_{i+1, j+1} \equiv R \pmod{HW + 1} が成立する。

各入力ファイルについて、テストケースを T 個解いてください。

制約

  • 1 \leq T \leq 100
  • 2 \leq H \leq 50
  • 2 \leq W \leq 50
  • 0 \leq R \lt HW + 1
  • 入力はすべて整数

部分点

この問題の満点は 101 点である。

  • 追加の制約 T = 1, H = W = 4, R = 8 を満たすデータセットに正解した場合は 10 点が与えられる。
  • 追加の制約 H = W を満たすデータセットに正解した場合は、追加で 90 点（計 100 点）が与えられる。

入力

入力は以下の形式で標準入力から与えられる。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

各ケースは、次の形式で与えられる。

H W R

出力

条件を満たす書き込み方が存在する場合は Yes を、存在しない場合は No を一行目に出力せよ。

さらに、条件を満たす書き込み方が存在する場合は、そのような書き込み方を、続く H 行に次の形式で出力せよ。

P_{1, 1} P_{1, 2} \cdots P_{1, W}
P_{2, 1} P_{2, 2} \cdots P_{2, W}
\vdots
P_{H, 1} P_{H, 2} \cdots P_{H, W}

条件を満たす書き込み方が複数存在する場合、そのどれを出力しても正解となる。

入力例 1

3
2 2 4
5 5 17
6 6 30

出力例 1

Yes
1 2
3 4
No
Yes
22 9 31 11 33 32
23 10 2 25 3 19
20 21 8 1 30 13
36 29 16 17 24 7
12 35 27 14 18 34
26 6 28 15 5 4

この入出力例は追加の制約 H = W を満たします。

入力例 2

6
2 3 4
13 11 0
3 8 5
20 24 39
21 3 32
3 13 0

出力例 2

Yes
2 5 4
6 1 3
No
Yes
1 19 13 18 14 21 17 22
5 9 10 2 20 16 15 23
7 12 11 4 3 8 24 6
No
No
Yes
1 2 3 6 7 9 11 13 14 17 18 19 21
5 8 15 16 25 24 35 32 10 4 20 12 30
22 23 26 27 28 29 31 33 34 36 37 38 39