Bob Roberts 是一位专门研究名为 Erauqs 的古老种族建筑的考古学家。这个古老种族不仅以其多年来积累的巨额财富而闻名，还以其建筑独特的房间布局而著称。他们的建筑总是矩形的，而建筑内部的房间总是正方形的。（为了保持这一特性，建筑中的某些区域被实心岩石填满。）

当 Bob 发现一座被掩埋的 Erauqi 建筑的痕迹时，他会先使用超声波设备在开始挖掘前尽可能多地了解建筑的布局。超声波可以告诉他任何宝藏的位置和岩石的位置，但其精度不足以确定墙壁的位置。然而，Bob 知道可以根据 Erauqs 总是在每个正方形房间里放置恰好一个宝藏这一事实来确定墙壁的位置。例如，如果超声波显示的宝藏和岩石位置如图 I.1 左侧所示，那么唯一可能的房间布局将如图右侧所示。

图 I.1：超声波结果与墙壁位置

偶尔，Bob 会遇到一个敌对部落 Elgnatcer 的建筑。在这种情况下，不可能找到符合 Erauqi 建筑原则的房间布局。

Bob 来找你编写一个程序，用来定位 Erauqi 正方形藏宝室的墙壁，并识别非 Erauqi 的建筑。坦率地说，这个问题让他感到非常头疼。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 100$)，表示建筑网格的行数和列数。接下来是 $n$ 行，每行包含 $m$ 个字符。这些字符为 ‘$’（宝藏）、‘#’（岩石）或 ‘.’（空地）。宝藏的数量至少为 1，且不超过 52 个。

输出格式

对于每个测试用例，如果无法将正方形房间分配给所有空地，使得每个房间恰好包含一个宝藏，则输出 elgnatcer。否则，输出一个 $n \times m$ 的网格，表示 Erauqi 建筑的布局。为每个正方形房间分配一个字母，顺序为 ‘A’，然后是 ‘B’，‘C’，...，‘Z’，‘a’，...，‘z’。房间标签的分配方式是：从最顶行（测试用例的第一行输入）开始，从左到右遍历每一行，每遇到一个未标记的房间，就为其分配下一个房间标签。输出中的每个网格方块应包含相应的房间标签或表示岩石的字符 ‘#’。

样例

输入格式 1

7 8
........
.$....$.
$...$...
......#$
.$....#$
...$....
$$.....$

输出格式 1

AABBBCCC
AABBBCCC
DDBBBCCC
DDEEEE#F
GGEEEE#H
GGEEEEII
JKEEEEII

输入格式 2

1 5
#$#$#

输出格式 2

#A#B#

输入格式 3

1 5
#$.$.

输出格式 3

elgnatcer