The Punctilious Cruciverbalist

A crossword puzzle is a grid of squares in which intersecting words are placed, one letter per square. Some squares are filled in black, which means no letter goes there. Solvers get clues for each word. Each clue is identified by a starting clue number and either Across (a horizontal word) or Down (a vertical word). Each square that can start a word gets a clue number. Numbers are assigned starting in the upper left and proceeding left to right, row by row. A square gets an Across clue number if the square to its left is black or off the grid. A square gets a Down clue number if the square above it is black or off the grid. See Figure E.1 for a simple example.

Will Longz solves crosswords and, like most solvers, tries first to solve clues where some letters are already present from solved clues that cross them. The closer those letters are to the start of the word, the better. Will uses a metric to choose the order of clues. If the answer to a clue spans $n$ squares, he assigns the value $n$ to the first square, $n-1$ to the second, and so on, ending with 1 for the last square. The rank of an unsolved clue is computed as follows. For each square that already has a letter, add its assigned value to a running total. Then divide that total by the sum of all values assigned to the clue. The result is the clue's rank. After ranking all unsolved clues, Will solves the clue with the highest rank. If there is a tie, he picks an Across clue over a Down clue. If there is still a tie, he picks the clue with the smallest starting clue number. After each clue is solved, Will recalculates the ranks before choosing the next clue.

In Figure E.1, the 6-Across clue has already been solved (written 6A). The 1-Down clue has values 3, 2, and 1 on its squares going down. Since its last square has a letter, its rank is $1/(3+2+1) = 1/6$. The ranks of 2D and 3D are $2/10$, and the rank of 5D is $2/6$. The unsolved Across clues 1A, 4A, and 7A all have rank 0. So Will solves 5D first, since we assume he can solve any clue. After that, the ranks of 4A and 7A become $1/10$ and $1/6$. Now 2D and 3D tie for the highest rank, and both are Down clues, so he picks the one with the lower clue number and solves 2D. The remaining clues are solved in this order, with each rank at the time of solving in parentheses: 7A (4/6), 4A (4/10), 3D (6/10), and 1A (3/6). Clue 5D is not on the list because the clues 4A, 6A, and 7A already fully determine it.

The first line contains two integers $r$ and $c$ ($1 \le r, c \le 50$), the number of rows and columns in the grid. The next $r$ lines each contain $c$ characters describing the puzzle. Each character is . for an empty square, # for a black square, or an uppercase English letter for a solved square. The grid always contains at least one empty square.

Print the order in which the unsolved clues should be solved, one per line. Each line contains the clue number followed by A for an Across clue or D for a Down clue.