마을 짓기

빛이 태어난 뒤, 사람들은 그것을 단지 비추는 존재가 아닌, 삶의 공간에 스며드는 힘으로 받아들이고자 했다.

그들은 빛이 모든 이에게 닿을 수 있는 새로운 마을을 꿈꾸었다. 그 꿈을 이루기 위해, 빛이 구석구석 스며들 수 있는 땅을 조심스레 골랐다.

그들이 선택한 빛의 땅을 되짚고, 흩어진 조각들을 이어 다시 그려보아라.

고대의 섬에는 $N$행 $M$열 크기의 격자 형태를 가진 토지가 있었다. 이때 위에서부터 $r$번째 행, 왼쪽에서부터 $c$번째 열의 칸을 $(r,c)$로 표기한다.

빛은 단단하게 굳은 토양 위에서는 흘러가지 못했고, 대신 부드럽고 투명한 땅을 따라 조용히 스며들었다. 사람들은 마을을 세우기 위해, 빛이 닿는 땅과 집을 지을 수 있는 땅을 구분했다.

사람들은 빛이 마을 전체에 스며들 수 있도록, 토지에서 다음 조건을 만족하는 구역을 골라 마을을 짓기로 결정했다.

• 마을을 지을 구역은 정사각형 모양이어야 한다.
• 구역의 주대각선에 있는 칸은 빛이 흐를 수 있어야 한다. (주대각선은 격자의 맨 왼쪽 위부터 오른쪽 아래를 잇는 대각선을 의미한다.)
• 주대각선을 제외한 나머지 칸들은 모두 집을 지을 수 있어야 한다.

다음은 $K=1,2,3$일 때 마을을 지을 수 있는 $K\times K$ 크기의 구역의 예시이다. 검은 칸은 빛이 흐를 수 있는 칸을, 하얀 칸은 집을 지을 수 있는 칸을 나타낸다.

아래와 같은 예시에서, 왼쪽 그림에 표시된 구역은 마을을 지을 수 있는 $4\times 4$ 크기의 구역이다. 하지만 오른쪽 그림에 표시된 구역의 경우, 주대각선이 아닌 칸에 집을 모두 지을 수 없으므로, 마을을 지을 수 없다.

마을을 지을 수 있는 구역의 개수를 크기별로 알아내어라.

첫 줄에는 토지의 크기를 나타내는 두 정수 $N$과 $M$이 공백으로 구분되어 주어진다.

이후 $N$개의 줄에 걸쳐, 그중 $i$번째 줄에는 칸 $(i,1) ,(i,2) ,\cdots ,(i,M)$의 땅의 유형을 나타내는 $M$개의 문자 $A_{i1},A_{i2},\cdots ,A_{iM}$가 주어진다. $A_{ij}$가 ‘X’라면 빛이 흐를 수 있는 칸이고, ‘.’라면 집을 지을 수 있는 칸이다.

$1$부터 $\min(N,M)$까지의 모든 정수 $K$에 대해, 마을을 지을 수 있는 $K\times K$ 크기의 구역의 수를 순서대로 한 줄에 하나씩 출력한다.

• $2\le N\le 2000$
• $2\le M\le 2000$
• $A_{ij}$는 ‘X’ 또는 ‘.’이다. $(1\le i\le N,1\le j\le M)$