산수화

윤이의 취미는 그림 그리기이다. 어느 날, 학교 뒷산을 보고 영감을 받은 윤이는 산수화 한 장을 그려 내었다. 산수화는 $N$행 $M$열의 격자 모양이며, 각 칸은 검은색 또는 흰색으로 칠해져 있다.

윤이는 산수화를 포닉스와 달구에게 선물하기로 했다. 그러나 그림은 한 장뿐이었고, 포닉스와 달구는 누가 그림을 가져야 하는지에 대한 토론을 시작했다. 토론은 쉽게 끝나지 않았는데 그 이유는 포닉스와 달구가 생각하는 좋은 산수화의 기준이 서로 다르기 때문이었다.

달구는 산이 많은 산수화를 좋은 산수화라고 생각하며, 포닉스는 호수가 많은 산수화를 좋은 산수화라고 생각한다. 산과 호수의 정의는 각각 아래와 같다. $(i,j)$는 $i$번째 행 $j$번째 열에 해당하는 칸을 의미한다.

• $a\le x,|a-x|+|b-y|\le d-1$를 만족하는 $(a,b)$가 모두 검은색이라면 이를 $(x,y)$를 중심으로 하고 크기가 $d$인 산이라 한다. 이때 $d$는 $1$ 이상 $\min(y,M-y+1,x)$ 이하의 정수여야 한다.
• $x\le a\le x+d-1,y\le b\le y+d-1$을 만족하는 $(a,b)$가 모두 흰색이라면 이를 $(x,y)$를 왼쪽 위 꼭짓점으로 하고 크기가 $d$인 호수라 한다. 이때 $d$는 $1$ 이상 $\min(N-x+1,M-y+1)$ 이하의 정수여야 한다.

위 그림의 경우, $(3,2)$를 중심으로 하고 크기가 $2$인 산과 $(1,3)$을 왼쪽 위 꼭짓점으로 하고 크기가 $2$인 호수가 있다.

윤이는 친구들의 토론을 멈추기 위해 $1$부터 $N$까지의 모든 $i$에 대해 크기가 $i$인 산의 개수와 호수의 개수를 직접 구해 주려 한다. 윤이를 도와 문제를 해결해 보자.

첫째 줄에 산수화의 행의 수 $N$과 열의 수 $M$이 공백으로 구분되어 주어진다. $(1 \le N, M \le 2000)$

둘째 줄부터 $N$줄에 걸쳐 산수화가 주어진다. $i+1$번째 줄에는 산수화의 $i$번째 행을 나타내는 길이가 $M$인 문자열이 주어진다. 모든 문자열은 # 또는 . 으로 구성된다. #은 검은색, .은 흰색을 의미한다.

첫째 줄에 크기가 $i$인 산의 개수를 나타내는 $N$개의 정수 $A\_1, A\_2, \cdots, A\_N$을 공백으로 구분해 출력한다.

둘째 줄에 크기가 $i$인 호수의 개수를 나타내는 $N$개의 정수 $B\_1, B\_2, \cdots, B\_N$을 공백으로 구분해 출력한다.