Byteland 国王决定将国家划分为若干个省份，每个孩子分一个省。

Byteland 的地图是一个由 $n$ 行 $m$ 列组成的矩形矩阵。国王的每个孩子都有一座城堡，位于矩阵的某个单元格中（每个单元格最多包含一座城堡）。国王希望按以下方式划分 Byteland：

• 每个省份必须是一个矩形。
• Byteland 领土的每个单元格必须恰好属于一个省份。
• 每个省份必须恰好包含一座城堡，即该省份所有者的城堡。

国王爱他所有的孩子，但其中一个是他的最爱。国王希望划分王国，使得属于他最爱孩子的省份面积尽可能大。你能帮他解决这个棘手的任务吗？

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 1000$)。

接下来的 $n$ 行每行包含 $m$ 个字符。每个字符代表矩阵的一个单元格。字符 . 代表一个空单元格，大写字母 'A' 到 'Z' 代表城堡。字母 'A' 对应国王最爱孩子的城堡。

所有字母均不相同。输入中恰好有一个字母 'A'。

输出格式

输出相同的矩阵，将每个字符 . 替换为该单元格所属省份所有者对应的小写字母。

样例

输入样例 1

6 8
......X.
.F......
...A....
........
.....P..
..L.....

输出样例 1

xxxxxxXx
fFaaaaaa
ffaAaaaa
ffaaaaaa
lllllPpp
llLllppp