Description
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? If so, how much time do they need?
There are some rules to follow:
The grass field is a rectangular area that consists of N × M 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 and Mmxl will never get out of the rectangular area. Notice that the sheep is captured only when she cannot move in her turn.
These little animals are very clever. If the wolves have a way to capture the sheep, they never miss the way. If the sheep is able to prevent being captured, she never make a mistake. Additionally, the wolves eager to capture the sheep as early as possible, and the sheep will try to delay the time being captured even if she cannot escape.
Input
Input contains multiple test cases. Each test case starts with two numbers N and M (1 ≤ N, M ≤ 10) in one line. Then N lines follow, each line has M characters, which describes the grass field. A ‘.’ denotes an empty grid, an ‘#’ denotes an obstacle, a ‘O’ denotes a baby wolf, and a ‘X’ denotes the Mmxl. There are exactly three ‘O’’s and one ‘X’.
Output
There is only one line for each test case. If lovely Mmxl will not be captured in finity rounds, print “Lucky Mmxl will never be captured:)”. If the wicked baby wolves are able to capture Mmxl, print “Poor Mmxl may be captured after xx steps:(” where xx is the number of turns after which the wolves can capture the sheep, which is certainly an odd number.
Sample Input
2 2
OO
OX
3 3
OOO
##X
...
3 3
OO#
###
.OX
3 4
OO##
####
..OX
4 4
OOO.
....
....
...X
5 5
O...O
.....
..#..
.....
O...X
5 5
O...O
.....
...#.
.....
O...X
6 6
......
.O..O.
..##..
..##..
.O..X.
......
6 6
#.....
.O..O.
..##..
..##..
.O..X.
......
10 10
..........
..........
..O....O..
..........
..........
..........
..........
..O....X..
..........
..........
10 10
..........
.#.#.#.#.#
..O.....O.
.#.#.#.#.#
..........
.#.#.#.#.#
..........
.#.#.#.#.#
..O.....X.
.#.#.#.#.#
Sample Output
Poor Mmxl may be captured after 1 steps:(
Poor Mmxl may be captured after 7 steps:(
Poor Mmxl may be captured after 5 steps:(
Lucky Mmxl will never be captured:)
Poor Mmxl may be captured after 21 steps:(
Lucky Mmxl will never be captured:)
Poor Mmxl may be captured after 41 steps:(
Lucky Mmxl will never be captured:)
Poor Mmxl may be captured after 39 steps:(
Lucky Mmxl will never be captured:)
Poor Mmxl may be captured after 51 steps:(
