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.