산수화

윤이의 취미는 그림 그리기이다. 어느 날, 학교 뒷산을 보고 영감을 받은 윤이는 산수화 한 장을 그렸다. 산수화는 $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$인 산의 개수 $A_i$를 공백으로 구분해 $N$개의 정수 $A_1, A_2, \cdots, A_N$으로 출력한다.

둘째 줄에 크기가 $i$인 호수의 개수 $B_i$를 공백으로 구분해 $N$개의 정수 $B_1, B_2, \cdots, B_N$으로 출력한다.