Susy is a beautiful and smart student. She is an expert  solving puzzle games, specially mazes, and such talent has given her several prizes from various competitions, where her speed and skills are tested.

Right now, she is participating in an special puzzle contests, and her jealous rival, Angelica, is participating too.

At this moment, they are in a tie, and in order to break this tie the judges have prepared a special round with a special game. The rules of this game are the following:

• The game consists of a table with walls, like a maze. Also, there are some special objects, the Magic Stones. To win the game, the player must take all the stones present in the table.
• There are four valid movements: Up, Down, Left and Right. Nevertheless, once the player choose a movement from his current position, he cannot stop moving in that direction until he crash with a wall in the maze. Obviously, the player cannot leave the table, so the limits of the table are considered walls too.
• As there can be many solutions, the judges want the optimal one, which mean the least number of moves.

This is not problem for Susy, but Angelica is having a really bad time with this game. Jealously, Angelica secretly took Susy's solution and cut it in many pieces (She is not very intelligent. She could copy the solution instead but her anger blinded her).

Time is running out, and Susy doesn't have the time required to solve the puzzle again. Fortunately, the participants can ask a friend to help with just one puzzle, and she knows something the judges don't, your programming skills.

Now, she is calling you! Write a program to solve the maze with the least moves possible! Help Susy!

Input

The input begins with two integer numbers, R and C, the number of rows and columns of the table respectively.

Next, there will be R lines with C characters each, representing the maze. Each maze will contain only following characters:

• "." - free space,
• "#" - wall,
• "S" - initial position of the player,
• "*" - magic stone.

Output

The output consists of 2 lines. The first must contain one only number S. S is the optimal solution of the game.

The next line consists of S strings separated with a "-". These strings are "Up", "Down", "Left" and "Right". The full string represents the movements done in the optimal solution.

If there is more than one optimal solution, you must print the lexicographically smallest one.

Example

Input:
5 6
*S....
....#.
.##...
**....
.#.*#.

Output:
7
Down-Right-Down-Left-Up-Left-Up

Constraints:

2 <= (r, c) <= 20. There will be no more than 13 magic stones in the maze.

NOTE: There will always be a solution for the given maze.