问题

有一个迷宫，其中有 $1$ 个起点和 $2$ 个目标点。迷宫由 $H$ 行和 $W$ 列的矩形单元格阵列组成。每个单元格都被指定为起点、目标点、通道或障碍物。设 $(r, c)$ 是第 $r$ 行、从左边数的第 $c$ 个单元格。

你将获得一个迷宫的地图。你必须在该地图中绘制两条从起点到每个目标点的路径。一条路径是一个以起点单元格开始、以目标点单元格结束、不包含障碍物单元格并且数组中相邻单元格对是相连的单元格的数组。一对单元格 $(a, b)$ 和 $(c, d)$ 是相邻的，如果 $|a-c|+|b-d|=1$。你绘制的路径必须满足以下条件。

• 每条路径必须包含尽可能少的单元格。这意味着每条路径都必须是从起点到每个目标点的最短路径。
• 为了使路径可区分，除了起点单元格之外，每条路径都不能有任何共同的单元格。

确定是否可以在给定的迷宫中找到满足条件的路径，并在可能的情况下在迷宫中显示路径。请阅读输入和输出部分以了解详细的格式。

输入

$H$ $W$ $s_{(1,1)}$$s_{(1,2)}$…$s_{(1,W)}$ $s_{(2,1)}$$s_{(2,2)}$…$s_{(2,W)}$ : $s_{(H,1)}$$s_{(H,2)}$…$s_{(1,W)}$

• 第一行包含两个整数 $H$, $W$ ($1 \\leq H, W \\leq 50$)，表示迷宫的大小。

• 接下来的 $H$ 行，每行包含长度为 $W$ 的字符串，表示迷宫的地图。第 $i$ 行（$1 \\leq i \\leq H$）的第 $j$ 个（$1 \\leq j \\leq W$）字符表示单元格 $(i, j)$。每个字符的含义如下。

  • . 表示单元格是通道单元格。
  • # 表示单元格是障碍物单元格。
  • S 表示单元格是起点单元格。
  • A 表示单元格是第一个目标点单元格。
  • B 表示单元格是第二个目标点单元格。

  保证字符 S、A、B 只出现一次。同时保证每个目标点至少有 $1$ 条路径。

输出

如果没有满足问题部分条件的路径，输出包含 NA 的 $1$ 行。

如果有满足条件的路径，输出 $H$ 行，每行由 $W$ 个字符组成。输出中第 $i$ 行（$1 \\leq i \\leq H$）的第 $j$ 个（$1 \\leq j \\leq W$）字符应表示迷宫中的单元格 $(i, j)$。输出必须满足以下条件。

• 输入中的通道单元格必须是 .、a 或 b 中的一个。
• 输入中的起点、障碍物或目标单元格必须与输入中的字符相同。
• 通过跟随相邻的 a 单元格，应能够从起点单元格到达目标单元格 A。a 单元格的数量必须尽可能少，以达到目标。
• 通过跟随相邻的 b 单元格，应能够从起点单元格到达目标单元格 B。b 单元格的数量必须尽可能少，以达到目标。

换句话说，用字符 a、b 显示到每个目标 A、B 的路径。如果有多个可能的答案，你可以选择其中任意一个。

请确保在输出的末尾插入换行符。

输入示例 1

5 5
..#..
.B.A#
...#.
.....
..S#.

输出示例 1

..#..
.BaA#
.ba#.
.ba..
.bS#.

输入示例 2

2 3
SBA
...

输出示例 2

NA

目标单元格不是障碍物，所以到达目标 A 的最短路径只有 $(1, 1)$ → $(1, 2)$ → $(1, 3)$。然而，该路径包含目标单元格 B，因此在最短路径中无法避免使用公共单元格。因此，应输出 NA。

输入示例 3

5 5
..#..
.B.A#
.#.#.
.....
..S#.

输出示例 3

NA

输入示例 4

5 8
.#...#..
.#.#.#..
.S.#...B
.#####A.
........

输出示例 4

.#bbb#..
.#b#b#..
aSb#bbbB
a#####A.
aaaaaaa.