题目描述

给定一个 $N$ 行 $M$ 列的 $01$ 矩阵 $A$。

对于矩阵中的两个元素 $A[i][j]$ 和 $A[k][l]$，定义它们之间的曼哈顿距离为：

$$\operatorname{dist}(A[i][j],A[k][l])=|i-k|+|j-l|$$

请你构造一个 $N$ 行 $M$ 列的整数矩阵 $B$，其中：

$$B[i][j]=\min_{\substack{1\le x\le N\\1\le y\le M\\A[x][y]=1}} \operatorname{dist}(A[i][j],A[x][y])$$

也就是说，$B[i][j]$ 表示矩阵中位置 $(i,j)$ 到最近的 $1$ 的曼哈顿距离。

输入格式

第一行输入两个整数 $N, M$，表示矩阵 $A$ 的行数和列数。

接下来 $N$ 行，每行包含一个长度为 $M$ 的 $01$ 字符串，表示矩阵 $A$。

输出格式

输出 $N$ 行，每行包含 $M$ 个整数，相邻整数之间用一个空格隔开。

第 $i$ 行第 $j$ 个整数表示 $B[i][j]$。

样例

3 4
0001
0011
0110

3 2 1 0
2 1 0 0
1 0 0 1

样例解释

矩阵为：

0 0 0 1
0 0 1 1
0 1 1 0

每个位置到最近的 $1$ 的曼哈顿距离如输出矩阵所示。

数据范围与提示

• $1 \le N, M \le 1000$
• 矩阵 $A$ 中至少存在一个元素为 $1$。