题目描述

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

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

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

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

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

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

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

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

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

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

输入格式

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

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

输出格式

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

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

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

3 2
#A
##
#A

#A
##
#A

3 3
AAB
A#B
ABB

#AA
###
BB#

提示

样例 #1 解释

激战结束后，战场的情况为

AA##H##B
BB######
########
#####AAA
####AAAA

右下角的 A 中，除了第 $5$ 行第 $5$ 列的 A 以外，下方或者上方都存在友方的士兵，故他们最终从战场中消失。最后战场如样例输出所示。

样例 #2 解释

注意只有在上方或下方有相邻的友方士兵时士兵才会从战场消失。

数据范围

对于所有数据，$1\le n,m\le 1000$，$s_{i,j}$ 为 A、B、H、# 中的一个，且每一行满足题目中的限制。具体测试点限制如下：

测试点编号	$n$ 的范围	$m$ 的范围	特殊性质
$1\sim 3$	$n=1$	$m\le100$	无
$4\sim 6$	$n\le100$	$m=1$
$7\sim 10$	$n\le 100$	$m\le100$	$s_{i,j}$ 不为 H
$11\sim 14$			$s_{i,j}$ 不为 B
$15,16$	$n\le100$	$m\le 100$	无
$17\sim 20$	$n\le 1000$	$m\le1000$