Landscape Painting

Yun's hobby is drawing. One day, inspired by the hill behind the school, Yun painted a landscape. The landscape is a grid of $N$ rows and $M$ columns, and each cell is painted black or white.

Yun decided to give the painting to Phoenix and Dalgu. However, there was only one painting, so Phoenix and Dalgu began arguing over who should get it. The debate did not end easily because the two had different standards for a good landscape.

Dalgu thinks a landscape with many mountains is good, and Phoenix thinks a landscape with many lakes is good. The definitions of a mountain and a lake are as follows. $(i,j)$ denotes the cell in row $i$ and column $j$.

• If every $(a,b)$ satisfying $a\le x,|a-x|+|b-y|\le d-1$ is black, this is called a mountain of size $d$ centered at $(x,y)$. Here $d$ must be an integer with $1 \le d \le \min(y,M-y+1,x)$.
• If every $(a,b)$ satisfying $x\le a\le x+d-1,y\le b\le y+d-1$ is white, this is called a lake of size $d$ with its top-left corner at $(x,y)$. Here $d$ must be an integer with $1 \le d \le \min(N-x+1,M-y+1)$.

In the figure above, there is a mountain of size $2$ centered at $(3,2)$ and a lake of size $2$ with its top-left corner at $(1,3)$.

To stop the debate, Yun wants to count, for every $i$ from $1$ to $N$, the number of mountains of size $i$ and the number of lakes of size $i$. Help Yun solve this problem.

The first line contains the number of rows $N$ and the number of columns $M$, separated by a space. $(1 \le N, M \le 2000)$

From the second line onward, the next $N$ lines describe the landscape. Line $i+1$ is a string of length $M$ representing row $i$ of the landscape. Every string consists of # or .. # means black, and . means white.

On the first line, print $N$ integers $A_1, A_2, \cdots, A_N$, separated by spaces, where $A_i$ is the number of mountains of size $i$.

On the second line, print $N$ integers $B_1, B_2, \cdots, B_N$, separated by spaces, where $B_i$ is the number of lakes of size $i$.