Background

Special for beginners, ^_^

Description

给出一个N*M的01矩阵，求每个点离它最近的数字1的点的距离是多少。距离是曼哈顿距离。(平面上，坐标（x1, y1）的点P1与坐标（x2, y2）的点P2的曼哈顿距离为：

|x1 - x2| + |y1 - y2|.)

Format

Input

第一行两个数N,M

后面N行，每行M个字符，为0或1

Output

共输出N行，每行M个数，用空格分开。

Samples

3 4
0001
0011
0110

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

Limitation

50%的数据,N,M<=100

100%的数据,N,M<=1000