该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

在风语谷，蛐蛐注意到一个奇妙的现象：这里的云朵都以匀速从西向东（从左到右）飘动。为了预测这些“行走”的云朵何时会飘过村庄的每一个角落，蛐蛐将整个区域划分成了一个 $n\times m$ 的网格，每个格子代表一小块区域。

题目描述

给定当前时刻每个格子是否有云朵，假设每朵云每分钟向东（右）移动一格，求对于每个格子，从现在起需要等待多少分钟才能第一次看到云朵。

• 如果格子当前就有云，输出 $0$；
• 如果格子永远不会有云抵达，输出 $-1$；
• 其他情况，输出等待的分钟数。

输入格式

第一行包含两个整数 $n$ 和 $m$，表示网格的行数和列数。
接下来 $n$ 行，每行包含 $m$ 个字符：

• c 表示该格子当前有云；
• . 表示该格子当前没有云。

输出格式

输出 $n$ 行，每行 $m$ 个整数，用空格分隔。第 $i$ 行第 $j$ 列的整数表示从现在起，第 $(i,j)$ 位置需要等待的分钟数（或特殊值）。

样例

6 8
.c......
........
.ccc..c.
....c...
..c.cc..
....c...

-1 0 1 2 3 4 5 6
-1 -1 -1 -1 -1 -1 -1 -1
-1 0 0 0 1 2 0 1
-1 -1 -1 -1 0 1 2 3
-1 -1 0 1 0 0 1 2
-1 -1 -1 -1 0 1 2 3

样例解释

• 第一行第 $2$ 列当前有云，所以输出 $0$；
• 第 $1$ 行第 $1$ 列左边再也没有云向东飘来，输出 $-1$；
• 第 $1$ 行第 $3$ 列需要等 $1$ 分钟（来自第 $2$ 列的云飘过来），以此类推。

数据范围

$1 \le n, m \le 100$

注意：请保证算法能够在 $O(nm)$ 时间内完成计算。