题目描述

$A$ 城和 $B$ 城在城市中激战，战场可以被视为一个 $n$ 行 $m$ 列的方阵。方阵中的每个方格中的信息为如下可能中的一个：

• #，代表空地；
• A，表示一位 $A$ 城的士兵；
• B，表示一位 $B$ 城的士兵；
• H，表示城墙。

方阵中行从上到下依次编号为 $1\sim n$，列从左到右依次编号为 $1\sim m$。

$A$ 城位于左侧，$B$ 城位于右侧。故对于每一行，$A$ 城的士兵全部位于 $B$ 城士兵的左侧。

对于每一行，城墙只可能出现在 $A$ 城士兵与 $B$ 城士兵的中间，即城墙的左侧只可能有 $A$ 城士兵，城墙的右侧只可能有 $B$ 城士兵。且，同一行最多有 $1$ 个方格是城墙。

激战开始，士兵们会根据地形指定战略。对于每一行：

• 如果该行有城墙，则士兵们会往自己城市方向后撤，在边界处整齐地排列；
• 否则，双方会进攻。对于人数较少的一方，士兵会全部倒下，从战场中消失。而另一方不会有士兵倒下，并且会冲至对方城市的方向，在边界处整齐地排列。特别地，如果这一行双方人数相等，则这一行所有士兵都会倒下。

随后激战结束。对于每个士兵会同时进行如下判断：

• 如果他的上方或下方有友方的士兵与他相邻，则他会从战场中消失，否则原地不动。

现在给你初始时的战场局面，请你输出最后战场的组成。

输入格式

第一行两个整数 $n,m$，表示方阵的行与列。

接下来 $n$ 行，第 $i$ 行一个长度为 $m$ 的字符串 $s_i$，其中第 $j$ 个字符 $s_{i,j}$ 表示第 $i$ 行第 $j$ 列的情况。

输出格式

共 $n$ 行，每行一个长度为 $m$ 的字符串，表示战场最终的情况。

样例 #1

样例输入 #1

5 8
#A#AH#B#
#A##B#B#
##AA##BB
AAA###BB
AAA#ABBB

样例输出 #1

AA##H##B
BB######
########
########
####A###

样例 #2

样例输入 #2

3 2
#A
##
#A

样例输出 #2

#A
##
#A

样例 #3

样例输入 #3

3 3
AAB
A#B
ABB

样例输出 #3

#AA
###
BB#

提示

数据范围

对于所有数据，$1\leq n,m\leq 1000$，$s_{i,j}$ 为 A、B、H、# 中的一个，且每一行满足题目中的限制。