# Crazy Robot solution codeforces

There is a grid, consisting of 𝑛n rows and 𝑚m columns. Each cell of the grid is either free or blocked. One of the free cells contains a lab. All the cells beyond the borders of the grid are also blocked.

A crazy robot has escaped from this lab. It is currently in some free cell of the grid. You can send one of the following commands to the robot: “move right”, “move down”, “move left” or “move up”. Each command means moving to a neighbouring cell in the corresponding direction.

However, as the robot is crazy, it will do anything except following the command. Upon receiving a command, it will choose a direction such that it differs from the one in command and the cell in that direction is not blocked. If there is such a direction, then it will move to a neighbouring cell in that direction. Otherwise, it will do nothing.

We want to get the robot to the lab to get it fixed. For each free cell, determine if the robot can be forced to reach the lab starting in this cell. That is, after each step of the robot a command can be sent to a robot such that no matter what different directions the robot chooses, it will end up in a lab.

Input Crazy Robot solution codeforces

The first line contains a single integer 𝑡t (1𝑡10001≤t≤1000) — the number of testcases.

The first line of each testcase contains two integers 𝑛n and 𝑚m (1𝑛,𝑚1061≤n,m≤106𝑛𝑚106n⋅m≤106) — the number of rows and the number of columns in the grid.

The 𝑖i-th of the next 𝑛n lines provides a description of the 𝑖i-th row of the grid. It consists of 𝑚m elements of one of three types:

• ‘.’ — the cell is free;
• ‘#’ — the cell is blocked;
• ‘L’ — the cell contains a lab.

The grid contains exactly one lab. The sum of 𝑛𝑚n⋅m over all testcases doesn’t exceed 106106.

Output

For each testcase find the free cells that the robot can be forced to reach the lab from. Given the grid, replace the free cells (marked with a dot) with a plus sign (‘+’) for the cells that the robot can be forced to reach the lab from. Print the resulting grid.

Example Crazy Robot solution codeforces

input

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


output

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

Note vCrazy Robot solution codeforces

In the first testcase there is no free cell that the robot can be forced to reach the lab from. Consider a corner cell. Given any direction, it will move to a neighbouring border grid that’s not a corner. Now consider a non-corner free cell. No matter what direction you send to the robot, it can choose a different direction such that it ends up in a corner.

In the last testcase, you can keep sending the command that is opposite to the direction to the lab and the robot will have no choice other than move towards the lab.

[Solution] Tree Coloring solution codeforces