题目描述

$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)$ に移動させることができるかを判定し、できる場合は操作回数の最小値を求めてください。

输入格式

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

$N$ $M$

输出格式

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

题目大意

题目描述

有一个大小为 $N\times N$ 的方格图（网格）。在本题中，我们所说的方格 $(i,j)$ 指网格从上往下数第 $i$ 行，从左往右数第 $j$ 列。

最开始，有一个棋子位于方格 $(1,1)$ 。现在你可以进行下面这个操作若干次：

• 当前棋子位于 $(i,j)$ ，那么移动它到一个距离它刚好 $\sqrt{M}$ 的点（不超出网格）。

本题中的“距离”，指欧几里得距离。即方格 $(i,j)$ 与 $(k,l)$ 的距离是 $\sqrt{(i-k)^2+(j-l)^2}$ 。

现在对于整个网格，请你确定棋子能否到达方格 $(i,j)$ 。如果可以，输出到达它的最少操作次数；如果不行，输出 -1 。

输入格式

输入两个正整数 $N$ ， $M$ 。

$N\ M$

输出格式

输出共 $N$ 行。 第 $i$ 行包含 $N$ 个整数，中间以一个空格隔开。如果棋子可以到达方格 $(i,j)$ ，第 $i$ 行第 $j$ 列应输出到达它的最少操作次数；如果不行，输出 -1 。

说明/提示

数据范围

• $1\ \le\ N\ \le\ 400$
• $1\ \le\ M\ \le\ 10^6$
• 输入全为整数

样例说明

对于样例1，你可以把棋子通过一定次数的操作挪到这个方格图的任意位置。

比如说，我们可以通过如下操作把棋子移到 $(2,2)$ ：

1. 开始棋子在 $(1,1)$ 。 $(1,1)$ 到 $(1,2)$ 的距离刚好是 $\sqrt 1$ ，所以我们把它移到 $(1,2)$ 。
2. 现在棋子在 $(1,2)$ 了。$(1,2)$ 到 $(2,2)$的距离也刚好是 $\sqrt 1$ ，所以我们就把它移到了 $(2,2)$ 。

3 1

0 1 2
1 2 3
2 3 4

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

提示

制約

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

Sample Explanation 1

駒は上下左右の $4$ 個のマスに移動することができます。 例えば $(2,2)$ に移動するには、以下のように $2$ 回の操作を行えばよいです。 - 今駒は $(1,1)$ に置かれている。$(1,1)$ と $(1,2)$ の距離はちょうど $\sqrt{1}$ であるため、駒を $(1,2)$ に移動させる。 - 今駒は $(1,2)$ に置かれている。$(1,2)$ と $(2,2)$ の距離はちょうど $\sqrt{1}$ であるため、駒を $(2,2)$ に移動させる。