给你一个 $N \times M$ 的矩阵 $A$，其中从 $1$ 到 $N \times M$ 的每个元素都恰好出现一次。 同时给你一个棋子“车”（rook），它最初位于包含数值为 $1$ 的元素的单元格中。此外，还给你一个整数 $K$。

如果以下条件均满足，车可以从单元格 $(r, c)$ 跳到单元格 $(r', c')$：

• $(r, c) \neq (r', c')$，即我们必须移动到一个不同的单元格，
• $r = r'$ 或 $c = c'$，即我们只能在同一行或同一列中移动，
• $0 < A[r'][c'] - A[r][c] \le K$。

对于矩阵中的每个单元格，求出车从包含 $1$ 的单元格出发到达该单元格所需的最少步数，如果根本无法到达，则说明其不可达。

实现细节

你需要实现以下函数：

int32[][] calculate_moves(int32[][] A, int32 K)

• A：长度为 $N$ 的数组，其元素为长度为 $M$ 的数组，描述网格图。
• K：移动限制。
• 该函数应返回一个长度为 $N$ 的数组，其元素为长度为 $M$ 的数组，包含从单元格 $1$ 到达该单元格所需的最少步数。如果某个单元格不可达，则该单元格对应的值应等于 $-1$。

数据范围

• $1 \le N, M \le 2\,500$
• $1 \le K \le N \cdot M$
• $1 \le A[i][j] \le N \cdot M$
• 每个介于 $1$ 到 $N \cdot M$ 之间的整数在 $A$ 中恰好出现一次。

子任务

样例

样例输入 1

calculate_moves([[8, 2, 4, 20, 5], [14, 13, 1, 19, 7], [15, 18, 12, 6, 11], [10, 9, 3, 16, 17]], 5)

样例输出 1

[[2, -1, 1, 6, 2],
 [4, -1, 0, 5, 3],
 [4, 5, 5, -1, 4],
 [3, -1, 1, -1, -1]]

说明

考虑以下调用：

calculate_moves([[8, 2, 4, 20, 5],
                 [14, 13, 1, 19, 7],
                 [15, 18, 12, 6, 11],
                 [10, 9, 3, 16, 17]], 5)

此时有 $N = 4, M = 5, K = 5$。

包含 $1$ 的单元格（即我们的起点）是 $A[1][2]$。因此，在 calculate_moves 返回的数组 $R$ 中，值 $R[1][2]$ 应等于 $0$，因为我们不需要进行任何移动即可到达该单元格。

为了到达 $A[3][0] = 10$，我们可以从 $A[1][2] = 1$ 移动到 $A[0][2] = 4$（因为它们在同一列，且 $4 - 1 = 3 \le 5$），然后从 $A[0][2] = 4$ 移动到 $A[0][0] = 8$（因为它们在同一行，且 $8 - 4 = 4 \le 5$），最后从 $A[0][0]$ 移动到 $A[3][0]$（因为它们在同一列，且 $10 - 8 = 2 \le 5$）。因此，在数组 $R$ 中，值 $R[3][0]$ 应等于 $3$。

请注意，无法以任何方式到达 $A[0][1] = 2$，因此值 $R[0][1]$ 应等于 $-1$。

样例评测程序

输入格式：

N M K
A[0][0] A[0][1] ... A[0][M-1]
A[1][0] A[1][1] ... A[1][M-1]
...
A[N-1][0] A[N-1][1] ... A[N-1][M-1]

输出格式：

R[0][0] R[0][1] ... R[0][M-1]
R[1][0] R[1][1] ... R[1][M-1]
...
R[N-1][0] R[N-1][1] ... R[N-1][M-1]

这里，$R$ 是 calculate_moves 返回的数组。