Kaeru Jump
В большом пруду живет лягушка, которая обожает прыгать по листьям лотоса, плавающим на поверхности. Эти листья обладают интересными особенностями: после того как лягушка спрыгивает с листа, он тонет. Листья расположены в виде сетки, как показано на рисунке ниже.
Рисунок 1: Пример расположения листьев
Лягушка придумала головоломку, используя эти особенности. В начале игры она находится на одном из листьев и смотрит в одном из четырех направлений: вверх, вниз, влево или вправо. Она может прыгать вперед, влево или вправо относительно своего текущего направления, но не назад или по диагонали. Например, если она смотрит влево, то может прыгнуть влево, вверх или вниз, но не вправо. Каждый прыжок приводит её на ближайший лист в направлении прыжка, и после этого она смотрит в этом направлении. Лист, с которого она прыгнула, исчезает в воде. Цель головоломки — прыгать с листа на лист, пока не останется только один лист.
Посмотрите пример на рисунке ниже.
В этой ситуации у лягушки есть три варианта: листья A, B и C. Она не может прыгнуть на лист D, так как прыжок назад невозможен. Предположим, она выбрала лист B. После прыжка ситуация изменится, как показано на следующем рисунке.
Теперь она может прыгнуть либо на лист E, либо на лист F.
Лягушка нашла эту головоломку сложной, так как в пруду много листьев. Можете ли вы помочь ей найти решение?
Входные данные
H W c_{1,1} ... c_{1,W} ... c_{H,1} ... c_{H,W}
Первая строка входных данных содержит два положительных целых числа H и W (1 ≤ H, W ≤ 10). Следующие H строк, содержащие по W символов каждая, описывают начальную конфигурацию листьев и лягушки с использованием следующих символов:
'.' : вода
'o' : лист
'U' : лягушка, смотрящая вверх (т.е. на верхнюю сторону) на листе
'D' : лягушка, смотрящая вниз (т.е. на нижнюю сторону) на листе
'L' : лягушка, смотрящая влево (т.е. на левую сторону) на листе
'R' : лягушка, смотрящая вправо (т.е. на правую сторону) на листе
Можно предположить, что в каждом вводе есть только одна лягушка. Также можно предположить, что общее количество листьев (включая лист, на котором изначально находится лягушка) не превышает 30.
Выходные данные
Выведите строку, состоящую из символов 'U' (вверх), 'D' (вниз), 'L' (влево) и 'R' (вправо), которая описывает серию движений. Вывод не должен содержать никаких других символов, таких как пробелы. Можно предположить, что для каждого ввода существует только одно решение.