Mario is one the most famous video games ever. In this problem, we will be helping Mario save the princess (again :P). In this game of Mario, each world will be represented by a 2-D rectangular grid. There are multiple worlds and all the worlds are of size R x C. The world contains many objects each covering exactly one cell.

The cell with 'S' denotes Mario's starting position. A cell with '.' denotes an empty cell over which Mario can walk safely. From that cell he can move to any of its 4 adjacent cells (which share an edge with it). A cell with 'D' denotes a pipe that leads to the world below. A cell with 'U' denotes a pipe that leads to the world above. If Mario enters a cell containing a pipe, he must enter the pipe. A cell with 'C' represents a coin and Mario collects these. After collecting the coin, the cell becomes an empty cell. A cell with '#' denotes bricks and Mario can't enter this cell no matter what. A cell with 'M' denotes the monster (Bowser), Mario has to defeat Bowser to save the princess. Mario initially start from an empty cell.

Our Mario is very determined and so he will be always able to defeat Bowser on a 1 on 1 battle. But he is greedy and will always want to collect all the coins before going to save the princess. If he is not able to collect all the coins, he won't save the princess!. Help Mario to find the minimum number of steps to do this feat.

Note: If 'U' is present in top-most world or 'D' is present in the bottom-most world, Mario can't enter the cell.

Input:

Input contains multiple test cases (will never exceed 1000).

First line of each test case will have 3 integers R, C and W.

'R x C' represents Grid dimension and 'W' represents number of worlds.

It will be followed by R x W lines. Each line will have 'C' characters.

First R lines describe the first world, second R lines describe the second world and so on upto W worlds.

Input ends by the line '0 0 0'.

Output:

For each test case, print a single line “Mario saved the princess in K steps” where K is the minimum number of steps if he defeat the monster else print “Mario failed to save princess”.

Constraints:

1 <= R, C <= 15

1 <= W <= 10

0 <= [Total number of coins] <= 10

All characters in the grid will be from the set {'S', '.', 'M', 'C', 'D', 'U', '#'}

Sample

Input:
2 2 1
SM
.D

2 2 2
SM
.D
C.
UC

3 3 2
S.M
C#.
D..
###
C.C
C.U

2 2 1
SM
#C

0 0 0

Output:
Mario saved the princess in 1 steps
Mario saved the princess in 7 steps
Mario saved the princess in 8 steps
Mario failed to save princess

Explanation for third test case:

Mario is in (0, 0, 1) (first world), the optimal path is (0, 0, 1) → (1, 0, 1) → (2, 0, 1) → (2, 0, 2) → (1, 0, 2) → (1, 1, 2) → (1, 2, 2) → (2, 2, 2) → (2, 2, 1) → (1, 2, 1) → (1, 2, 0). So totally 10 steps which includes 1 Up and 1 Down. As there is no manpower required for Mario to take step in between the worlds omitting the 2 steps which gives us the answer 8.