Beaming With Joy (Large)

Joy is leaving on a long vacation, so she hired technicians to install a security system built on infrared laser beams. The technicians gave her a diagram of the house: a grid of unit cells with $R$ rows and $C$ columns. Each cell holds one of the following.

• /: a two sided mirror that runs from the lower left corner of the cell to its upper right corner.
• \: a two sided mirror that runs from the upper left corner of the cell to its lower right corner.
• -: a beam shooter that fires horizontal beams into the cells immediately to its left and to its right, when those cells exist.
• |: a beam shooter that fires vertical beams into the cells immediately above it and below it, when those cells exist.
• #: a wall. The house is not necessarily surrounded by a border of walls, which is one reason Joy needs a security system.
• .: an empty cell.

A beam travels in a straight line and passes through empty cells. When a beam hits a mirror, it turns 90 degrees off the surface of the mirror and continues. A beam traveling right that hits / starts traveling up, and a beam traveling up, left, or down that hits / starts traveling right, down, or left. A beam traveling right, up, left, or down that hits \ starts traveling down, left, up, or right. A beam stops when it hits a wall or leaves the grid. Beams may cross each other. If a beam reaches any beam shooter, including the shooter that fired it, that shooter is destroyed.

Joy wants at least one beam to pass through every empty cell, and she wants no shooter destroyed. The technicians already installed the system, so the only change left to her is rotating some of the shooters by 90 degrees: for any number of shooters, including zero, she can turn - into | or turn | into -. She does not have to minimize the number of rotations.

Decide whether Joy can reach her goal, and print the resulting grid when she can.

The first line has the number of test cases $T$. Each test case starts with a line holding two integers $R$ and $C$, the number of rows and the number of columns of the grid. Then $R$ lines of $C$ characters each follow, and every character is /, \, -, |, #, or ..

Limits

• $1 \le T \le 100$
• $1 \le R \le 50$
• $1 \le C \le 50$
• Every grid character is one of /, \, -, |, #, ..
• The number of beam shooters in one grid, that is the number of - characters plus the number of | characters, is between 1 and 100.
• Every grid has at least one . character.

For each test case, print one line Case #x: y, where $x$ is the test case number starting from 1, and $y$ is IMPOSSIBLE when Joy cannot reach her goal and POSSIBLE when she can. When she can, print after that line the resulting grid as $R$ lines of $C$ characters. The resulting grid is the input grid with zero or more - characters changed to | and zero or more | characters changed to -, and every other character left alone.

More than one grid can work. In that case print the lexicographically smallest one. Compare two grids as the strings formed by concatenating their $R$ rows from top to bottom, and compare characters by ASCII code, so - (45) comes before | (124).