题目描述

Byteland 的国王准备把国家划分成若干省份，每个孩子拥有一个省份。

国家地图是一个 $n\times m$ 的矩形网格。每个孩子都有一座城堡，位于某个格子中，并且每个格子最多只有一座城堡。

国王要求划分满足：

1. 每个省份必须是一个轴对齐矩形；
2. 每个格子恰好属于一个省份；
3. 每个省份恰好包含一座城堡，该城堡对应的孩子就是这个省份的主人。

国王最喜欢的孩子的城堡用字母 A 表示。

你需要构造一种合法划分，使 A 所属省份的面积尽可能大。

输入格式

第一行两个整数 $n,m$：

接下来 $n$ 行，每行包含 $m$ 个字符：

• . 表示空格；
• A～Z 表示某个孩子的城堡。

所有出现的字母互不相同，并且恰好有一个 A。

输出格式

输出同样大小的 $n\times m$ 网格。

原有的大写字母保持不变；每个原本为 . 的格子，替换为该格所属省份主人对应字母的小写形式。

输出必须表示一个满足题目全部条件的划分，并且 A 所属省份的面积必须最大。

样例

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

xxxxxxXx
fFaaaaaa
ffaAaaaa
ffaaaaaa
lllllPpp
llLllppp