题目内容

在一个 $n$ 行 $m$ 列的矩形营地上，每个格子只能是补给站（用字符 '0' 表示）或空地（用字符 '1' 表示）。对于营地中的任意一个格子，定义它的“补给距离”为：从该格子出发，每次可以向上、下、左、右四个方向之一移动一步，走到某个补给站所需的最少步数。如果格子本身已经是补给站，则补给距离为 $0$。

请你求出营地中每个格子的补给距离。

保证 $1 \le n, m \le 10^3$，且营地中至少存在一个补给站。

输入描述

第一行包含两个整数 $n$ 和 $m$，分别表示营地的行数和列数。 接下来的 $n$ 行，每行包含一个长度为 $m$ 的字符串，字符串仅由字符 '0' 和 '1' 组成，其中 '0' 表示补给站，'1' 表示空地。

输出描述

输出共 $n$ 行，每行 $m$ 个整数，相邻整数之间用一个空格分隔。其中第 $i$ 行的第 $j$ 个整数表示营地中第 $i$ 行第 $j$ 列格子的补给距离。

样例1

输入

3 3
111
101
111

输出

2 1 2
1 0 1
2 1 2

说明

营地大小为 $3 \times 3$，正中央的格子为补给站（用 0 表示），其余均为空地（用 1 表示）。

补给站自身距离为 0。与补给站相邻的上、下、左、右四个格子只需 1 步即可到达，因此补给距离为 1。四个角落的格子需要先走到相邻的边界格子再进入补给站，共需 2 步，因此补给距离为 2。

样例2

输入

2 4
0101
1010

输出

0 1 0 1
1 0 1 0

说明

营地大小为 $2 \times 4$，补给站与空地交替出现。

第一行的第 1、3 列以及第二行的第 2、4 列均为补给站，补给距离为 0。其余格子均与某个补给站相邻，只需 1 步即可到达，因此补给距离为 1。

样例3

输入

1 1
0

输出

0

说明

边界情况：营地仅包含 $1 \times 1$ 的一个格子，且该格子本身即为补给站。因此该格子的补给距离为 0。