L タイリング

$N\times N$ のグリッドの上から $r$ 行目、左から $c$ 列目のマスを $(r,c)$ とする。

長さ $X$ の L タイルは、中心のマス $1$ つと、中心から互いに垂直な $2$ 方向にそれぞれ $X$ 個ずつ一直線に連なるマスからなる。全部で $2X+1$ マスであり、自由に回転させることができる。 長さ $$ のタイルが つずつある。すべてのタイルをグリッドに沿って置け。タイルは盤の外にはみ出したり互いに重なったりしてはならず、覆われないマスは ただ つでなければならない。

可能な配置を $1$ つ求めるか、不可能であることを判定せよ。

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

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

各テストケースについて、配置が存在しない場合は $1$ 行に -1 を出力せよ。

配置が存在する場合は、$N$ 行にそれぞれ $N$ 個の整数を出力せよ。$i$ 行目の $j$ 番目の整数は $(i,j)$ を覆うタイルの長さである。 には を出力せよ。

• $1\leq T\leq100\,000$.
• $1\leq N\leq1000$.
• $1\leq R,C\leq N$.