십자말풀이 번호 매기기

베시는 십자말풀이 퍼즐을 좋아한다. 그런데 언니 엘시가 퍼즐책에 우유를 쏟아서 번호가 모두 지워졌고, 이제 각 단서가 어디서 시작하는지 알아볼 수 없다. 베시를 도와 단서의 번호를 다시 매기자.

번호가 하나도 없는 $N \times M$ 격자가 주어진다. 각 칸은 비어 있거나(하얀 칸) 막혀 있다(검은 칸). 번호는 다음 두 단계로 매긴다.

1단계. 각 칸이 가로 단서의 시작점인지, 세로 단서의 시작점인지 판정한다. 어떤 칸이 가로 단서의 시작점이려면 그 칸이 비어 있고, 왼쪽 칸이 막혀 있거나 격자 밖이며, 오른쪽으로 이어지는 두 칸이 모두 격자 안에 있으면서 비어 있어야 한다. 즉 가로로 놓이는 단어는 세 글자 이상이다. 세로 단서의 시작점도 모양이 같다. 그 칸이 비어 있고, 위쪽 칸이 막혀 있거나 격자 밖이며, 아래로 이어지는 두 칸이 모두 격자 안에 있으면서 비어 있어야 한다.

2단계. 시작점으로 판정한 칸에 번호를 매긴다. 순서는 책을 읽는 순서와 같다. 위쪽 행부터 아래쪽 행으로 가고, 같은 행에서는 왼쪽 칸부터 오른쪽 칸으로 간다. 한 칸이 가로 단서와 세로 단서의 시작점을 동시에 만족해도 번호는 하나만 매긴다.

다음 격자를 보자.

...
#..
...
..#
.##

시작점인 칸을 !로 표시하면 이렇게 된다.

!!!
#..
!..
..#
.##

번호를 매기면 이렇게 된다.

123
#..
4..
..#
.##

주어지는 격자가 출판되는 십자말풀이의 규칙을 따르지 않을 수도 있다. 예를 들어 어떤 단서에도 속하지 않는 빈 칸이 있을 수 있다.

첫 줄에 격자의 행 개수 $N$과 열 개수 $M$이 공백으로 구분되어 주어진다. $3 \le N \le 50$, $3 \le M \le 50$이다.

다음 $N$개의 줄에 격자의 각 행이 주어진다. 각 줄은 $M$개의 문자로 이루어지며, 각 문자는 빈 칸을 뜻하는 .이거나 막힌 칸을 뜻하는 #이다.

첫 줄에 번호를 매긴 칸의 개수를 출력한다.

이어서 시작점인 칸의 위치를 번호 순서대로 한 줄에 하나씩 출력한다. 한 줄에는 행 번호와 열 번호를 공백으로 구분해 출력한다. 맨 위 왼쪽 칸이 $(1, 1)$이고 맨 아래 오른쪽 칸이 $(N, M)$이다.

번호를 매긴 칸이 없으면 첫 줄에 0만 출력한다.