ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Novosibirsk SU contest. Petrozavodsk training camp. Summer 2007

About     Problems     Submit solution     Judge status     Standings
Contest is over

D. Find the Treasure!

Time limit: 5.0 second
Memory limit: 64 MB
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 ≤ 6). Next 3N 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.


Win 5
Lose 1


Please note that in the sample input all spaces were replaced by full stop symbols '.' for clarity only.
Problem Source: Novosibirsk SU Contest. Petrozavodsk training camp, September 2007
To submit the solution for this problem go to the Problem set: 1555. Find the Treasure!