题目描述

小方块和小三角在一个 $N\times M$ 的矩形棋盘上玩 Jumpy 游戏。

棋盘中的每个格子要么是墙，要么是空格。每个空格还具有蓝、红、绿三种颜色之一。游戏开始时，所有空格均为蓝色，Jumpy 从某个空格出发。

两名玩家轮流控制 Jumpy：

• 小方块只能进行水平方向的跳跃，即向左或向右；
• 小三角只能进行竖直方向的跳跃，即向上或向下。

一次跳跃不要求只移动到相邻格子，可以跨过若干个空格，但不能穿过墙。跳跃终点也允许与起点相同。

Jumpy 落到一个格子后：

• 若终点是红色，当前行动的玩家立即失败；
• 若终点是绿色，当前行动的玩家立即获胜；
• 若终点是蓝色，则先把起点染成绿色，再把终点染成红色，然后游戏继续。

染色发生在落地之后，因此不会改变本次落到红色或绿色格子时的即时胜负。若起点与终点相同，染色顺序仍然是先绿后红，因此顺序非常重要。

对棋盘上的每个空格，以及两种可能的先手玩家，判断在双方都采取最优策略时谁能够获胜。

输入格式

第一行包含两个整数 $N,M$，表示棋盘大小。

接下来 $N$ 行，每行包含 $M$ 个字符：

• . 表示空格；
• # 表示墙。

输出格式

输出 $N$ 行，每行 $M$ 个字符。

• 若该格是墙，输出 #；
• 若无论谁先手都不能获胜，输出 N；
• 若两名玩家分别先手时都能获胜，输出 B；
• 若只有小方块先手时能获胜，输出 S；
• 若只有小三角先手时能获胜，输出 T。

数据范围

• $1\le N,M\le500$。

子任务

样例 1

输入：
9 9
....#..#.
.####..#.
.......#.
.#..#.##.
.#..#....
########.
....#....
##.##.##.
.......#.

输出：
BSSS#TT#T
T####TT#T
BSBBSBB#T
T#BB#T##T
T#BB#BSSB
########T
SSBS#BSSB
##B##B##T
SSBSSBS#T

样例 2

输入：
5 5
...#.
.###.
...#.
##.#.
.....

输出：
BSS#T
B###T
BBB#T
##B#T
SSBSB