题目描述

给定一个 $N$ 行 $M$ 列的 $0-1$ 矩阵 $A$，$A[i][j]$ 与 $A[k][l]$ 之间的曼哈顿距离定义为：

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

求一个与矩阵 $A$ 大小相同的矩阵 $B$，其中：

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

输入格式

第一行，两个整数 $N,M$，中间用一个空格隔开。 随后有 $N$ 行，每行 $M$ 个数，表示矩阵 $A$。

输出格式

$N$ 行，每行 $M$ 个数，表示矩阵 $B$。

样例

3 4
0001
0011
0110

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

提示

$1 \le N,M \le 1000$。