N - All Crosses Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

N 行 M 列のマス目に整数を書き込む方法のうち、以下が成り立つものが存在するか判定し、存在する場合は 1 個構築してください。

ここで、A_{i,j} を上から i 番目、左から j 番目のマスに書かれた整数とします。

  • A_{i,j} は 0 以上 X-1 以下である。
  • A_{i,j} \equiv A_{i-1,j} + A_{i+1,j} + A_{i,j-1} + A_{i,j+1}\ (\bmod X)
  • \displaystyle \sum_{i=1}^{N} \sum_{j=1}^{M} A_{i,j} > 0

ただし、A_{0,i},A_{N+1,i},A_{i,0},A_{i,M+1} は全て 0 とします。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 1 \le T \le 100
  • 1 \le N,M,X \le 100
  • 1 個の入力ファイルに対する N の総和は 100 以下である。
  • 1 個の入力ファイルに対する M の総和は 100 以下である。
  • 入力は全て整数である。

入力

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

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

それぞれのテストケースは以下の形式で与えられる。

N M X

出力

i 個目のテストケースに対する解を \mathrm{ans}_i とした時、以下のように出力してください。

\mathrm{ans}_1
\mathrm{ans}_2
\vdots
\mathrm{ans}_T

それぞれのテストケースに対しては、以下のように出力してください。

条件を満たす整数の書き込み方が存在しないのであれば、-1 を、そうでないならば以下の形式で出力してください。

A_{1,1}\ A_{1,2}\ \dots\ A_{1,M}
A_{2,1}\ A_{2,2}\ \dots\ A_{2,M}
\vdots
A_{N,1}\ A_{N,2}\ \dots\ A_{N,M}

入力例 1

3
2 2 3
2 2 2
52 53 2

出力例 1

2 1 
1 2 
-1
-1

1 個目のテストケースについて、これは条件を満たす書き込み方です。例えば、A_{1,1} \equiv A_{0,1} + A_{2,1} + A_{1,0} + A_{1,2} \ (\bmod X) となっています。

2,3 個目のテストケースについて、条件を満たす書き込み方は存在しません。