Magic Labyrinth
There is a magic labyrinth. Very scary monsters live in this labyrinth. The labyrinth is divided on squares. Each square either is free or contains an obstacle. Free squares can be either dangerous or safe. Starting at some free square and moving only through free squares, your goal is to reach some safe square as soon as possible. Each move you make is "U", "D", "L", "R", denoting up, down, left, and right respectively.
Nothing happens (your position does not change) if you move into an obstacle, or try to leave the labyrinth. Similarly, nothing happens if you try to move and you have already reached safe square (you never leave safe position).
You know labyrinth structure well, but unfortunately you do not know which position you start at. Find the shortest sequence of moves, leading you to safe square, regardless of your initial position.
Input
The first line of input contains two integers M and N, giving the number of rows and columns in the labyrinth respectively (1 ≤ M, N ≤ 5). Each of following M lines contains a string of length N, consisting of characters "." (free danger square), "*" (free safe square) or "#" (obstacle). These strings specify the map of the labyrinth.
Output
Output a single line containing the shortest sequence of moves, leading to safe square. If there are multiple shortest sequences, output the one that is lexicographically smallest. If there is no valid solution, output "NO SOLUTION" instead.