填字游戏由一个网格组成，网格中放置着相互交叉的单词，每个方格填入一个字母。有些网格方格被涂黑，表示此处不应填入字母。解题者会收到每个单词的线索，每个线索由一个起始线索编号和“横向”（Across，用于水平单词）或“纵向”（Down，用于垂直单词）标识。每个可以作为单词起点的方格都会被赋予一个线索编号，编号从左上角开始，按行从左到右递增。如果一个方格的左侧是黑色方格或网格边界，则该方格包含一个横向线索编号；如果一个方格的上方是黑色方格或网格边界，则该方格包含一个纵向线索编号。简单示例见图 E.1。

图 E.1：填字游戏示例。

Will Longz 是一位狂热的填字游戏爱好者，和大多数解题者一样，他首先尝试解决那些已经填入部分字母的线索（这些字母来自已经解出的、与当前线索相交的线索）。通常，这些已知字母越靠近单词的开头越好。Will 开发了一种指标来帮助他决定解决线索的顺序。如果一个线索的答案跨越 $n$ 个方格，他将 $n$ 分配给第一个方格，$n-1$ 分配给第二个方格，依此类推，最后一个方格分配到 $1$。任何未解线索的排名定义如下：对于每个已经填有字母的方格，将其分配的值加到总和中。然后将此总和除以分配给该线索的所有值的总和，得到该线索的排名。完成所有线索的计算后，Will 会解决排名最高的线索。如果出现平局，他会优先选择横向线索而非纵向线索。如果仍然平局，他会选择起始线索编号最小的线索。每解决一个线索后，Will 都会重新计算排名，然后再选择下一个排名最高的线索。

例如，考虑图 E.1 中的填字游戏，其中 6-Across 线索（我们简称为 6A）已经解出。为了确定 1-Down (1D) 线索的排名，Will 首先为向下的每个方格分配值 3、2 和 1。由于最后一个方格中已有字母，该线索的排名为 $1/(3 + 2 + 1) = 1/6$。同样，他确定 2D 和 3D 的排名为 $2/10$，5D 的排名为 $2/6$。三个未解横向线索 1A、4A 和 7A 的排名均为 0。因此，下一个要解决的线索是 5D（我们保持乐观，始终假设 Will 可以解决任何线索）。一旦解出，4A 和 7A 的排名分别变为 $1/10$ 和 $1/6$。由于现在排名最高的线索（2D 和 3D）之间出现平局，且它们都是纵向线索，Will 会选择线索编号最小的纵向线索并解决 2D。以此类推，剩余线索按以下顺序解决（括号内为解出时的排名）：7A (4/6)、4A (4/10)、3D (6/10) 和 1A (3/6)。注意，线索 5D 不在列表中，因为它已被之前解出的线索（即 4A、6A 和 7A）完全解出。

对于本题，你将获得一个填字游戏网格，其中包含零个或多个已填好的方格，你必须确定未解线索的解决顺序。已填好的方格可能对应也可能不对应完全解出的线索。最后一个转折点是：我们只会提供网格中的黑色方格和字母。你必须确定线索编号（我打赌 Will 能做到！）。

输入格式

输入的第一行包含两个整数 $r$ 和 $c$ ($1 \le r, c \le 50$)，指定填字游戏网格的行数和列数。接下来是 $r$ 行，每行包含 $c$ 个字符，描述该谜题。每个字符要么是 '.'（表示空方格），要么是 '#'（表示黑色方格），要么是一个大写英文字母（表示已解出的方格）。网格中至少会有一个空方格。

输出格式

按顺序显示应解决的线索，每行一个，使用上述指标。每个线索应以线索编号开头，后跟字母 'A' 或 'D'（分别代表横向或纵向线索）。

样例

样例输入 1

4 4
...#
....
JAVA
#...

样例输出 1

5D
2D
7A
4A
3D
1A