题目描述

在一个矩形培养皿中有 $n$ 排细胞，每一排从左往右排列着一共 $m$ 个细胞。

我们用不同的字符表示不同的细胞：

• 'A'：表示被病毒感染的细胞，一开始培养皿中恰好只有一个被病毒感染的细胞；
• 'O'：表示活动细胞，如果活动细胞的周围与它相邻（即上一排、下一排、同一排左边和右边最多四个）的细胞被感染了，那么活动细胞马上也会被感染；
• 'X'：表示顽强细胞，顽强细胞不会被感染病毒，同时它也不会传播病毒，可以起到很好的阻隔病毒的作用。

初始时培养皿中只有一个细胞被病毒感染，但此时的培养皿可能处在不稳定状态。我们说培养皿处在不稳定状态，指的是培养皿中存在至少一个活动细胞，它的上下左右与它相邻的细胞中存在被病毒感染的细胞，此时这个活动细胞马上也会转变为被病毒感染的细胞。

当所有的被病毒感染的细胞的上下左右相邻的细胞都不是活动细胞时，该培养皿将会处于一个稳定状态。

你需要计算并输出稳定状态时培养皿中每个细胞的情况。

输入格式

第一行，两个整数 $n$ 和 $m$（$1 \le n,m \le 1000$），表示培养皿中有几排细胞，以及每一排有几个细胞。

接下来 $n$ 行，每行包含一个长度为 $m$ 的字符串。表示这个培养皿中初始时的情况。

数据保证恰好有一个字符 'A'。

输出格式

输出共 $n$ 行，每行包含一个长度为 $m$ 的字符串，用于表示处于稳定状态时培养皿中每个细胞的情况。

5 6
AOO#OO
OO#OOO
O#OOOO
OO#OOO
OOO#OO

AAA#OO
AA#OOO
A#OOOO
AA#OOO
AAA#OO

7 8
OOOOOOOO
O######O
OOOOAOOO
O######O
OOOOOOOO
########
OOOOOOOO

AAAAAAAA
A######A
AAAAAAAA
A######A
AAAAAAAA
########
OOOOOOOO

说明/提示

数据规模与约定

• 对于 $30\%$ 的数据，$n,m \le 10$
• 对于 $60\%$ 的数据，$n,m \le 100$
• 对于 $100\%$ 的数据，$1 \le n,m \le 1000$