闪烁

时间限制：1000MS 512MB

题目描述

给定一 $n$ 行 $m$ 列的棋盘，棋盘的每个格子都有一非负整数权值，第 $i$ 行第 $j$ 列的格子（记作 $(i,j)$ ）的权值为 $c_{i,j}$ 。

Putata和Budada将使用该棋盘进行回合制游戏，游戏规则如下：

• 棋盘上恒有一枚棋子，且总是位于棋盘上的某个格子内。
• 初始时，随机决定Putata和Budada谁先手，并随机决定棋子的初始位置（记作 $(i_s,j_s)$ ）；
• Putata和Budada将轮流行动，每次行动使棋子移动一步，直至触发某个游戏结束条件；
• 棋子的移动规则：当棋子位于 $(i,j)$ 且 $c_{i,j}>0$ 时，其可移动至 $(i+c_{i,j},j),(i-c_{i,j},j),(i,j+c_{i,j}),(i,j-c_{i,j})$ 四者中任一实际存在的格子（即 $i' \in [1,n] \land j' \in [1,m])$ ，但不能停留在原地；若4个格子都不存在或 $c_{i,j}=0$ ，棋子不可移动。
• 游戏结束条件：
  • 在任意时刻下：
    • 当棋子位于 $(1,1)$ 时，游戏结束，判Putata获胜，Budada失败；
    • 否则当棋子位于 $(n,m)$ 时，游戏结束，判Budada获胜，Putata失败；
    • 否则当棋子不可移动时，游戏结束，判当前需要移动棋子的人失败；
  • 否则当双方已移动棋子共计 $10^{100}$ 次时，游戏强制结束并判双方平局。

双方都足够聪明，且会全力争取尽量好的游戏结果（能取胜就取胜，否则能平局就平局）；请对于每种先后手情况和每个可能的棋子初始位置判断游戏的最终结果。

输入描述

第一行含一个整数 $t$ ，表示测试用例的个数；对于每组测试用例：

共输入 $n+1$ 行：

• 第一行含两个正整数 $n$ 和 $m$ ，以空格分隔，依次代表棋盘的行数和列数；
• 接下来 $n$ 行，每行含 $m$ 个非负整数，以空格分隔；第 $i$ 行第 $j$ 列的数为 $c_{i,j}$ 。

输出描述

对于每组测试用例：

共输出 $2n$ 行：

• 每行输出一个长为 $m$ 的字符串，表示各情况下的游戏结果；
• 对于前 $n$ 行，第 $i$ 行的字符串的第 $j$ 个字符代表Putata先手而棋子初始位于 $(i,j)$ 的游戏结果：P代表Putata获胜，B代表Budada获胜，T代表平局；
• 对于后 $n$ 行，第 $i$ 行的字符串的第 $j$ 个字符代表Budada先手而棋子初始位于 $(i,j)$ 的游戏结果，表达方式同上。

输入样例

3
3 3
1 1 1
1 1 0
1 1 1
3 4
0 2 2 2
2 1 1 2
2 2 1 0
1 3
1 10 1

输出样例

PPP
PPB
TTB
PPB
TBP
TBB
PBPT
BTTB
PTBB
PTBB
TBBT
BBBB
PBB
PPB

数据范围

数据范围：

• $1 \le t \le 5 \times 10^4$
• $1 \le n,m \le 10^5 , 2 \le n \times m \le 10^5$
• $\sum n,\sum m,\sum n \times m \leq 10^5$
• $0 \le c_{i,j} \le 10^9$