Vasya and Petya play the following board turn-based game. It is played
in the maze formed by the square board with N × N
cells. Every cell can have a wall on each of four sides, so between two adjacent
cells two walls can exist. Also each player has bazooka loaded with one rocket.
If player has a rocket she can launch it into five directions (north, east,
south, west and downwards). If rocket is fired downwards, the player who
launched it dies. In the other case rocket flies until it leaves the maze
or hits the wall or another player. In the case of hitting a wall it is
destroyed and in the case of hitting a player she dies. On each turn corresponding
player can move to adjacent cell (if it is not occupied by another player and
there is no wall between cells), pass move or fire a rocket if she has it. If one player dies the other wins the game. Another way to win is to take a chest with a treasure
placed in the maze and step outside the board. To take a chest player has to
just move to the cell containing it. Player cannot step outside the board if she has no chest.
After playing this game many times with different mazes Vasya noted that
Petya always wins. Now he wishes to find optimal strategy for the game to
figure out wherever he can beat Petya. So he asked you to write a program to
solve this problem. Consider both players use optimal strategy.
The first line of the input contains single integer N
(2 ≤ N
lines contain 3N
characters each. They describe the maze in such
a way that every cell is described by the 3 × 3 square. On the picture
below the cell surrounded by 4 walls is depicted. The question mark is
replaced by either space or digit '1' or '2' or asterisk ('*'; ASCII 42) in the
input. The digit stands for corresponding player, asterisk — for the chest and
space — for empty cell. The horizontal wall is '-'
(ASCII 45) and the vertical
wall is '|' (ASCII 124). North is on top.
It is guaranteed that '1', '2' and '*' will appear in the input only once. The
total number of walls in the input will not exceed 30.
In the case of tie output must contain single line containing "Draw". In the
other case the first line of the output must contain the result of the game for
the first player ("Win" or "Lose") and the minimal number of turns necessary to get
corresponding result of the game (the second player tries to maximize this number)
separated by single space. The second line must contain the first move for the first
player. Moves are described by two characters. First of them can be either 'M' which
stands for moving and 'S' which stands for shooting. The second character can be one
of the '2', '4', '8', '6', '5' where '2' is south, '4' is west, '8' is north, '6' is
east. In the case of moving '5' means passing move and in the other case '5' means suicide.
Please note that in the sample input all spaces were replaced by full stop symbols
'.' for clarity only.
Источник задачи: Novosibirsk SU Contest. Petrozavodsk training camp, September 2007