根号 M 跳跃

题目描述

有一个 $N \times N$ 的网格。我们用 $(i, j)$ 表示从上数第 $i$ 行、从左数第 $j$ 列的格子。

最初,一枚棋子放在 $(1, 1)$。你可以任意多次重复以下操作:

设棋子当前所在的格子为 $(i, j)$。将棋子移动到与 $(i, j)$ 的距离恰好为 $\sqrt{M}$ 的格子。

这里,我们定义格子 $(i, j)$ 与格子 $(k, l)$ 之间的距离为 $\sqrt{(i-k)^2+(j-l)^2}$。

对于所有格子 $(i, j)$,判断棋子能否到达 $(i, j)$。如果能够到达,求出所需的最少操作次数。

输入格式

输入按以下格式从标准输入给出:

$N$ $M$

输出格式

输出 $N$ 行。第 $i$ 行应包含 $N$ 个整数。如果棋子能到达 $(i, j)$,则第 $i$ 行中的第 $j$ 个整数应为到达所需的最少操作次数;否则,应为 $-1$。

样例

3 1

0 1 2
1 2 3
2 3 4

你可以将棋子移动到四个相邻的格子。

例如,可以按如下方式用两次操作将棋子移动到 $(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

数据范围

• $1 \le N \le 400$
• $1 \le M \le 10^6$
• 输入中的所有值均为整数。