[2010Beijing wc]矩阵距离

给定一个 $n$ 行 $m$ 列的矩阵，其中每个元素的值均为 $0$ 或 $1$。

定义矩阵中两个位置 $(i,j)$ 与 $(x,y)$ 之间的距离为：

$$D((i,j),(x,y))=|i-x|+|j-y|。$$

对于矩阵中的每个位置 $(i,j)$，求其到所有值为 $1$ 的位置的最小距离，即：

$$\min_{\substack{1\le x\le n\\1\le y\le m\\a_{x,y}=1}}D((i,j),(x,y))。$$

所有下标均从 $1$ 开始。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示矩阵的行数和列数。

接下来 $n$ 行，每行包含 $m$ 个字符。其中，第 $i$ 行的第 $j$ 个字符表示 $a_{i,j}$，每个字符均为 $0$ 或 $1$。

输出格式

输出 $n$ 行，每行包含 $m$ 个以空格分隔的整数。其中，第 $i$ 行的第 $j$ 个整数表示位置 $(i,j)$ 到任意值为 $1$ 的位置的最小距离。

样例输入

3 4
0001
0011
0110

样例输出

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

数据范围

• 对于 $100\%$ 的数据，$0<n,m\le 1000$；
• 保证矩阵中至少有一个元素的值为 $1$。

来源与许可

本题为 Beijing WC 2010 试题「矩阵距离」，题面与测试数据整理自 BZOJ。

样例 1

输入

3 4
0001
0011
0110

输出

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