有一个网格,由 $$$n$$$ 行和 $$$m$$$ 列组成。网格的每个单元格要么空闲,要么被阻塞。其中一个空闲牢房包含一个实验室。网格边界之外的所有单元格也被阻挡。
一个疯狂的机器人逃离了这个实验室。它当前位于网格的某个空闲单元中。您可以向机器人发送以下命令之一:“向右移动”、“向下移动”、“向左移动”或“向上移动”。每个命令都意味着移动到相应方向的相邻小区。
然而,由于机器人很疯狂,除了听从命令之外,它会做任何事情。接收到命令后,它将选择一个与命令中的方向不同的方向,并且该方向上的小区不会被阻塞。如果有这样的方向,那么它就会移动到该方向的相邻小区。否则,它什么也做不了。
我们希望将机器人送到实验室进行修复。对于每个空闲单元,确定是否可以强制机器人从该单元开始到达实验室。也就是说,在机器人的每一步之后,都可以向机器人发送命令,这样无论机器人选择什么不同的方向,它最终都会进入实验室。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 10^6$$$; $$$n \cdot m \le 10^6$$$) - 网格中的行数和列数。
接下来的 $$$n$$$ 行的第 $$$i$$$ 行提供了网格第 $$$i$$$ 行的描述。它由以下三种类型之一的 $$$m$$$ 元素组成:
- '.' — 细胞是免费的;
- '#' — 单元格被阻止;
- 'L' — 该单元包含一个实验室。
网格仅包含一个实验室。所有测试用例的 $$$n \cdot m$$$ 总和不超过 $$$10^6$$$。
输出
对于每个测试用例,找到机器人可以被迫到达实验室的空闲单元。给定网格,将空闲单元(用点标记)替换为加号(“+”),作为机器人可以被迫到达实验室的单元。打印生成的网格。
示例
输入 #1
4 3 3 ... .L. ... 4 5 #.... ..##L ...#. ..... 1 1 L 1 9 ....L..#.
输出 #1
... .L. ... #++++ ..##L ...#+ ...++ L ++++L++#.
注意
在第一个测试用例中,没有可以强制机器人到达实验室的空闲单元。考虑一个角单元。给定任何方向,它都会移动到不是角点的相邻边界网格。现在考虑一个非角自由单元。无论您向机器人发送哪个方向,它都可以选择不同的方向,使其最终到达角落。
在最后一个测试用例中,你可以继续发送与实验室方向相反的命令,机器人将别无选择,只能向实验室移动。