The Unstoppable Robot

A group of students was developing a robot that can move in a maze. Yet, the robot is not perfect and cannot change its direction or stop until reaching a wall or an obstacle. So, when the robot starts moving, it has to get to the nearest wall in its current direction and then pick a new direction.

You are asked to find what would be the minimum number of moves for the robot to get from the starting position S to the end position E and print the commands the students need to send to the robot for it to accomplish that:

L - move left

U - move up

R - move right

D - move down

Input

The first line of the input contains two numbers h and w (2 ≤ h, w ≤ 100) the height and the width of the grid.

The next h lines contain w characters representing the grid:

. is the floor

# is a wall

S is the starting point

E is the endpoint

It’s guaranteed that the grid is surrounded by walls making sure the robot doesn’t get outside the grid.

Output

The program should print the minimum number of moves to get from the starting position to the ending one on the first line. The second line should contain all the commands the students need to send to the robot. In case there are several solutions, the program can print any of those.

If it’s impossible for the robot to get to the end, the program should print Impossible.

Examples

Input

7 9
#########
#.......#
#.S.....#
#.......#
#.#E....#
#.#.....#
#########

Output

4
RDLU

Hint

You can treat the starting point as a floor (.) and the ending point as a wall (#).

Input

Output

Examples

Constraints

To check your solution you need to sign in

Sign in to continue