2252 - [2010Beijing wc]矩阵距离

假设我们有矩阵,其元素值非零即1 a11…… a1m ……………. an1…….anm

?定义aij与akl之间的距离为D(aij,akl)=abs(i-k)+abs(j-L) ??

Input

输入文件的第一行为两个整数，分别代表n和m。 接下来的n行，第i行的第 j个字符代表aij

Output

输出包含N行，每行M个用空格分开的数字，其中第i行第J个数字代表 Min(D(aij,axy) 1<=x<=N 1<=y<m,且axy=1

Examples

Input

3 4 
0001 
0011 
0110

Output

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

Hint

对于100%的数据，满足 0 <? ? m n <=1000

Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题