RoboRace

There is a robot race organized by the Department of Computer Science and Robotics at ACME University. Each robot designed by the students will have to move from point A to point B in some room filled with obstacles. Your friend is a student there and he wants to win the race. He has already built and programmed his robot. However, a couple of hours ago, he has learned that the rules of the competition have changed. The robots will not be judged based on how fast they reach the target, but they will be ranked according to the lexicographic order of the trajectories they take and they are not allowed to step on the same spot more than once. Your friend has panicked and has asked you to write a new program for his robot.

Input

The input to your program will consist of several test cases. In the first line of each test case there will be two positive integers H < 129 and W < 33. The description of the room will follow. It will consist of H lines, W characters in each. Character '#' will correspond to a wall or obstacle, '.' will be empty space, 'A' will be the start point, and 'B' will be the end point.
There will be exactly one 'A' character and exactly one 'B' character.
The first and last column and the first and last row of the map will only have '#' characters.
You are guaranteed that point B will be reachable from point A.
After the last test case there will be a line with two zeroes.

Output

For each test case, you need to output a line with a single string describing a trajectory for the robot to reach point B, starting from point A. The trajectory will consist of letters 'U' for up, 'D' for down, 'L' for left, 'R' for right. Each of the letters corresponds to a single move on the map.
The trajectory has to be the first possible trajectory from A to B in the lexicographic order. The robot cannot enter the same location more than once (this applies to point A as well).

Sample input

8 8
########
#.A....#
#......#
#...#..#
#......#
#......#
#B...#.#
########
7 5
#####
#...#
#...#
#B.A#
#...#
#...#
#####
0 0

Sample output

DDDDDL
DDLLURUL