꼼꼼한 십자말풀이꾼

십자말풀이 퍼즐은 교차하는 단어를 칸에 넣은 격자이며, 칸마다 글자가 하나씩 들어갑니다. 검은색으로 칠한 칸에는 글자를 넣지 않습니다. 풀이자는 단어마다 힌트를 받으며, 각 힌트는 시작 번호와 Across(가로 단어) 또는 Down(세로 단어)으로 구분합니다. 단어를 시작할 수 있는 칸에는 번호를 붙입니다. 번호는 왼쪽 위에서 시작해 행마다 왼쪽에서 오른쪽으로 매깁니다. 왼쪽 칸이 검은 칸이거나 격자 밖이면 그 칸에 Across 번호가 붙고, 위쪽 칸이 검은 칸이거나 격자 밖이면 Down 번호가 붙습니다. 간단한 예시는 그림 E.1을 참고하세요.

Will Longz는 십자말풀이를 즐기는 사람입니다. 대부분의 풀이자처럼 그도 이미 풀린 힌트와 겹쳐서 일부 글자가 채워진 힌트부터 풉니다. 채워진 글자가 단어의 앞쪽에 가까울수록 좋습니다. Will은 힌트를 푸는 순서를 정하기 위해 다음 지표를 씁니다. 힌트의 답이 $n$칸에 걸쳐 있으면 첫 칸에 $n$을, 둘째 칸에 $n-1$을 주고, 이런 식으로 마지막 칸에 1을 줄 때까지 이어 갑니다. 풀지 않은 힌트의 순위는 다음과 같이 구합니다. 이미 글자가 있는 칸마다 그 칸에 준 값을 더해 누적합을 구합니다. 그 누적합을 이 힌트에 준 값의 총합으로 나눕니다. 이렇게 얻은 값이 힌트의 순위입니다. 풀지 않은 모든 힌트의 순위를 구한 뒤, Will은 순위가 가장 높은 힌트를 풉니다. 순위가 같으면 Down 힌트보다 Across 힌트를 먼저 고릅니다. 그래도 같으면 시작 번호가 가장 작은 힌트를 고릅니다. 힌트를 하나 풀 때마다 Will은 순위를 다시 계산한 뒤 다음 힌트를 고릅니다.

그림 E.1에서는 6A가 이미 풀려 있습니다. 1D는 아래로 내려가는 칸에 3, 2, 1의 값이 붙습니다. 마지막 칸에 글자가 있으므로 순위는 $1/(3+2+1) = 1/6$입니다. 2D와 3D의 순위는 각각 $2/10$이고, 5D의 순위는 $2/6$입니다. 풀지 않은 가로 힌트 1A, 4A, 7A는 모두 순위가 0입니다. Will은 어떤 힌트든 풀 수 있다고 가정하므로 5D를 먼저 풉니다. 그 뒤 4A와 7A의 순위는 각각 $1/10$과 $1/6$이 됩니다. 이제 2D와 3D가 가장 높은 순위로 동점이며, 둘 다 세로 힌트이므로 번호가 더 작은 2D를 풉니다. 나머지 힌트는 다음 순서로 풀립니다. 괄호 안은 풀 때의 순위입니다. 7A(4/6), 4A(4/10), 3D(6/10), 1A(3/6). 5D는 4A, 6A, 7A로 이미 완전히 정해지므로 목록에 없습니다.

첫 줄에 격자의 행 수와 열 수를 나타내는 정수 $r$과 $c$가 주어집니다($1 \le r, c \le 50$). 이어서 $r$줄에 걸쳐 각각 $c$개의 문자로 퍼즐이 주어집니다. 각 문자는 빈 칸을 뜻하는 ., 검은 칸을 뜻하는 #, 또는 채워진 칸을 뜻하는 대문자 영문자 중 하나입니다. 격자에는 빈 칸이 항상 하나 이상 있습니다.

풀지 않은 힌트를 풀어야 하는 순서를 한 줄에 하나씩 출력합니다. 각 줄에는 힌트 번호를 쓰고, 가로 힌트이면 A, 세로 힌트이면 D를 이어서 씁니다.