2013
11-28

# The Wolves and the Sheep

Nalim, Ocis and Remmarguts are playing on grass, and they feel very hungry now. As baby wolves, they decide to capture a little sheep to eat. Fortunately, they immediately discover a sheep roaming around the grass. However, what they found is the queen of the sheep —- Mmxl, who has extraordinary speed that can compare with the wolves, and is very clever! Can you judge whether the baby wolves will capture Mmxl!

There are some rules to follow:
The grass field is a rectangular area that consist of R * C grids. And some obstacles like stones or trees exist. The actions of the baby wolves and Mmxl are taken in rounds. In each round, baby wolves take actions first, and then Mmxl follows. In the baby wolves’ turn, the three wolves will make a decision, and choose one of them to move (a move means moving from a grid to a neighboring grid). There must be a wolf to move, unless none of them can move. In the Mmxl’s turn, she will always move. If she cannot move, she is captured. Baby wolves and Mmxl cannot move to the grids on which there are obstacles, and they are always on different grids. Baby wolves will never get out of the rectangular area. Once Mmxl gets away from the grass, she is never captured.

You should notice that the only situation that Mmxl is captured is that she cannot move, but is not that in wolves’ turn, some wolf is in the neighboring grid of Mmxl’s.

Input contains multiple test cases. Each test case starts with two numbers R and C (1 <= R, C <= 10) in one line. Then R lines follow, each line has C characters, which describes the grass field. A ‘.’ denotes an empty grid, an ‘X’ denotes an obstacle, a ‘W’ denotes a baby wolf, and a ‘S’ denotes the Mmxl. There are exactly three ‘W’ and one ‘S’. Every test case will be followed by a blank line.

There is only one line for each test case. If lovely Mmxl will not be captured in finity rounds, print "Lucky Mmxl is safe:)". If the wicked baby wolves are able to capture Mmxl, print "Poor Mmxl is in danger:(".

3 5
XXW.X
XWSWX
XXX.X

4 5
XXWXX
XWSWX
XX.XX
XX.XX

7 6
XXXXXX
XWWW.X
X....X
X....X
X....X
X...SX
XXXXXX

7 7
XXXXXXX
XWWW..X
X.....X
X..X..X
X.....X
X....SX
XXXXXXX

7 7
XXXXXXX
XWWW..X
X.....X
X..XX.X
X.....X
X....SX
XXXXXXX

10 10
WWW.......
..........
..........
..........
..........
.....S....
..........
..........
..........
..........

9 9
XXXXXXXXX
X...X...X
XW.....WX
X.X...X.X
X..X.X..X
X...S...X
XXXXXXXXX
XWXXXXXXX
XXXXXXXXX

9 9
XXXXXXXXX
X.......X
XW.....WX
X.X...X.X
X..X.X..X
X...S...X
XXXXXXXXX
XWXXXXXXX
XXXXXXXXX

9 9
XXXXXXXXX
....X....
XW.....WX
X.X...X.X
X..X.X..X
X...S...X
XXXXXXXXX
XWXXXXXXX
XXXXXXXXX

3 3
WX.
XSX
WXW

Lucky Mmxl is safe:)
Lucky Mmxl is safe:)
Poor Mmxl is in danger:(
Lucky Mmxl is safe:)
Poor Mmxl is in danger:(
Lucky Mmxl is safe:)
Poor Mmxl is in danger:(
Lucky Mmxl is safe:)
Lucky Mmxl is safe:)
Poor Mmxl is in danger:(