In a galaxy far far away from our’s, there lived a team of scientists who invented a device that could kill all computervirusses that do terrible things to MS-DOS computers. This device could do its job in the entire universe because it used a magic laser beam. But, just like in all great devices, this device had a strange component in it. This component is a two-dimensional maze with black holes and mirrors in it. Nobody knew the reason for this component but the scientists said it was a crucial component. This maze has two openings in it. One of these openings is in front of the magic laser. All the mirrors in the maze have two reflecting sides. These mirrors always make an angle of 45 degrees with the laser beam but they can be rotated over 90 degrees, so each mirror can be in 2 states only. The laser beam will be totally absorbed by a black hole. The laser beam may cross itself (with an angle of 90 degrees) in an empty place of the maze. In this problem you are given several mazes (one at a time) in which you have to position the mirrors in such a way that the laser beam can travel from one entrance to the other. The border of each maze is marked by black holes (except for two places which are the two entrances of the maze). The mirrors in the given mazes will probably not have a correct angle to reflect a laser beam from one entrance of the maze to the other. The mirrors in the given mazes can be positioned in such a way that a laser beam can travel through the maze. Your program must read the mazes from the input file and position the mirrors in it in such a way that a laser beam that enters through one entrance exits through the other. Input The input for your program is a textflle. This file contains severas mazes. A specification of a single maze is given by the following description: • First a line that contains two positive integers (say M and N) separated by one space which specify the number of columns and the number of rows (in that order) of the maze to come. These integers can have a value from 3 to 50 inclusive. • On the next N lines follows the maze with the mirrors and black holes. Mirrors are given by a ‘\’ (backslash) or a ‘/’ (divide). Here ‘\’ and ‘/’ correspond to the 2 states of a mirror. Black holes are given by ‘*’ (star). Empty places in the maze are given by dots. The last line of the input file is given by ‘-1 -1’. Output The output file is a textfile which contains the resulting mazes. The mazes in the output file must be separated from each other by one empty line. Sample Input 45 **** / *./. ..
2/2 .* 44 .* *.* \ *. -1 -1 Sample Output
/* .. .. . . *.* \ *.