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' (вправо), який описує серію рухів. Вихід не повинен містити жодних інших символів, таких як пробіли. Можна припустити, що для кожного вхідного набору даних існує лише одне рішення.