Background

Special for beginners, ^_^

Description

M国战俘被关押在K国的集中营，为了防止战俘闹事，每个房间只关正好一名战俘。集中营的形状是长方形的，里面每个房间都是正方形的。为了保证这一特性，建筑中有些位置用建筑垃圾堆满。现在M过的中央情报局通过热成像设备拍摄了监狱的照片，并从照片确定了每个战俘的位置，为了更好的开展营救工作，需要确定每堵墙的位置，现在就请你编个程序帮助确定每个房间的位置。

Format

Input

输入第一行包含两个数n和m（1 ≤ n, m ≤ 100），表示集中营网格化以后的行数和列数。后面n行，每行m个字符。字符只能是‘$’、‘#’或者‘.’中的一种，分别表示战俘、建筑垃圾、空的空间。最少1个战俘，最多52个战俘。

Output

对于每个测试点，如果不存在一种正方形的牢房分配方法使得正好每间牢房恰好一个战俘，则输出“elgnatcer”。否则，输出n*m的矩阵表示集中营的牢房布局图，每个正方形牢房用一个字母命名，从'A'到'Z'，大写字母用完再用小写字母。按照从上到下，同一行内从左到右的顺序分配牢房的字母编号，左上角命名为'A'，然后每碰到一间新的牢房就用下一个没有用过的字母命名。输出的每个网格中或者是字母命名的牢房名或者是表示堆满建筑垃圾的'#'。

Samples

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

AABBBCCC
AABBBCCC
DDBBBCCC
DDEEEE#F
GGEEEE#H
GGEEEEII
JKEEEEII

Limitation

0.2s, 1024KiB for each test case.