题目描述

有一个网格，由 $n$ 行和 $m$ 列组成。网格的每个单元格要么是空的，要么是一堵墙。其中有一个空单元内有一个实验室。网格边界外全部是墙。

一个故障机器人从一个实验室逃了出来。它目前在网格的某个空单元中。你可以向机器人发送以下命令之一：“向右移动”、“向下移动”、“向左移动”或“向上移动”。每个命令意味着移动到相应方向的相邻单元格。

然而，由于机器人故障了，除了听从命令，它什么都会做。收到命令后，它将选择一个与命令方向不同的可通行的方向。如果找不到不听指令的移动方法，那么它什么都不做。

我们想让机器人到达实验室从而可以修理它。对于每个空单元，确定机器人是否可以从该单元开始到达实验室。也就是说，在机器人的每一步之后，都可以向机器人发送一个命令，使得无论机器人选择什么方向，它最终都能进入实验室。

输入格式

本题有多组数据。

第一行包含一个整数 $T$，表示数据组数。

每个测试样例的第一行包含两个整数 $n$ 和 $m$，表示网格中的行数和列数。

接下来有 $n$ 行，每行表示网格的一行，包括 $m$ 个 $C_{i,j}$ 字符。包括以下三种类型之一：

• . — 单元格是空的；
• # — 单元格被阻塞；
• L — 单元格内有一个实验室。

题目保证网格仅包含一个实验室。

输出格式

对于每个测试样例，找到可以使机器人到达实验室的空格。对于原网格图，将可以到达实验室的空格替换为加号 (+)，打印新的网格。

4
3 3
...
.L.
...
4 5
#....
..##L
...#.
.....
1 1
L
1 9
....L..#.

...
.L.
... 
#++++
..##L
...#+
...++
L
++++L++#.

提示

【样例解释】

在第一个测试样例中，没有可以使机器人到达实验室的空格。考虑一个角空格。给定任何方向，它将移动到相邻的边界空格。现在考虑一个非角空格。无论你向机器人发送什么方向，它都可以选择不同的方向，这样它就会走回角落里。

在最后一个测试样例中，您可以继续向机器人发送与实验室方向相反的命令，机器人将别无选择，只能向实验室移动。

【数据范围】

对于 $20\%$ 的数据：$1 \leq T \leq 10, 1 \leq n, m \leq 10$；

对于另外 $20\%$ 的数据：$n, m$ 至少有一个为 $1$；

对于 $100\%$ 的数据：$1 \leq T \leq 10000, 1 \leq n, m \leq 10^6$，且对于 $T$ 组样例中 $n \times m$ 的总和小于等于 $10^6$。$C_{ij}$ 属于 $\{\tt{., \#, L}\}$，且有且仅有一个 $C_{ij} = \tt L$。