402579: GYM100812 F Graveyard of Bandits

The rain still didn't want to stop, as well as my damned life. My target was Dragon — bandit and murderer called so since he alone set fire to the entire town with all its citizens. Good Magician remained my last clue. It's hardly possible that he knew something, but there was no choice.

After economic collapse Good Magician retired and got a job as a watchman at the Central Graveyard. The former chief advisor of the King now digged graves and dusted cold gravestones. I was walking through the graveyard, and my legs were drowning in the shaky ground, which seemed to be calling me to stay. Finally, I saw the Good Magician studying the map of the graveyard.

I said I was looking for Dragon, and he replied that in that case it would be reasonable for me to reserve a piece of land on his graveyard. I would have answered with a smile if I had remembered how. He said he was busy with solving a very important problem and couldn't get distracted.

The graveyard was a checkered field of size n × m cells. One grave, depending on the size of the coffin, could occupy a rectangle of one cell width and some cells length. There were a lot of different creatures in Fairy Kingdom so the lengths of coffins could vary a lot. For each possible length of a grave, Good Magician wanted to calculate how many different variants there were to allocate land for that grave, taking into account that some cells could be already occupied by other graves. The old man was for sure crazy, but I decided to help him so that we could get to the business sooner.

The first line contains two integers separated by a space: n and m (1 ≤ n, m ≤ 10⁵, n × m ≤ 10⁶) — the sizes of the graveyard in cells.

The next n lines contain m characters each — the map of the graveyard. The i-th line on its j-th position has character «.», if the corresponding cell is free and can be used for a grave, or character «+», if the corresponding cell is occupied.

Output integers separated by spaces. On the k-th position output the number of different ways to dig a grave of length k.

3 4
...+
.+.+
+++.

6 4 1 0

4 3
...
.+.
.+.
...

10 10 6 2