配点 : $400$ 点

問題文

$N \times N$ のマス目があります。上から $i$ 行目、左から $j$ 列目のマスを $(i,j)$ と表します。

始め、$(1,1)$ に駒が $1$ 個置かれています。あなたは以下の操作を何度でも行うことができます。

• 今駒が置かれているマスと距離がちょうど $\sqrt{M}$ であるマスに駒を移動させる。

ここで、マス $(i,j)$ とマス $(k,l)$ の距離は $\sqrt{(i-k)^2+(j-l)^2}$ とします。

全てのマス $(i,j)$ に対して、以下の問題を解いてください。

• 駒を $(1,1)$ から $(i,j)$ に移動させることができるかを判定し、できる場合は操作回数の最小値を求めてください。

制約

• $1 \le N \le 400$
• $1 \le M \le 10^6$
• 入力は全て整数

入力

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

$N$ $M$

出力

$N$ 行出力せよ。$i$ 行目には $N$ 個の整数を出力せよ。$i$ 行目の $j$ 個目の出力は、マス $(i,j)$ に駒を移動させることができるのであれば操作回数の最小値を、そうでないのであれば $-1$ を出力せよ。

3 1

0 1 2
1 2 3
2 3 4

駒は上下左右の $4$ 個のマスに移動することができます。

例えば $(2,2)$ に移動するには、以下のように $2$ 回の操作を行えばよいです。

• 今駒は $(1,1)$ に置かれている。$(1,1)$ と $(1,2)$ の距離はちょうど $\sqrt{1}$ であるため、駒を $(1,2)$ に移動させる。
• 今駒は $(1,2)$ に置かれている。$(1,2)$ と $(2,2)$ の距離はちょうど $\sqrt{1}$ であるため、駒を $(2,2)$ に移動させる。

10 5

0 3 2 3 2 3 4 5 4 5
3 4 1 2 3 4 3 4 5 6
2 1 4 3 2 3 4 5 4 5
3 2 3 2 3 4 3 4 5 6
2 3 2 3 4 3 4 5 4 5
3 4 3 4 3 4 5 4 5 6
4 3 4 3 4 5 4 5 6 5
5 4 5 4 5 4 5 6 5 6
4 5 4 5 4 5 6 5 6 7
5 6 5 6 5 6 5 6 7 6