Сусіднє село

Обмеження: 2 сек., 256 МіБ

А тим часом Андрій Старобувний святкував свої іменини: зібралися вони з друзями та й поїхали в сусіднє село. Добряче відсвяткувавши, Андрійко попрощався і вирішив прямувати додому. Але це виявилось не так і просто — чи то через втому, чи то пива (чи чим то там у тому селі святкують?) було трішки забагато, а втім, наш герой зовсім забув, у який бік йому йти. Добре, що він завбачливо взяв із собою карту, на якій були позначені дороговкази, що мали б вивести з чужого села. Отак помалу прямуючи до першого вказівника, Андрій задумався над тим, скільки ж йому доведеться пройти, поки він не покине межі чужого села?..

Карта в іменинника прямокутна, розділена на одиничні квадрати. Кожен квадрат може містити інформацію про те, в якому напрямі треба рухатися, щоб вийти з села. Як тільки Андрій попадає у квадрат з вказівником, він обов’язково слідує у вказаному напрямі, поки не зустріне інший вказівник або не вийде за межі села.

Вам дано цю карту і початкове місцезнаходження Андрія. Напишіть програму, яка визначить відстань, що необхідно пройти нашому герою, щоб покинути чуже село.

Вхідні дані

У першому рядку задано два цілі числа — висоту карти \(n\) та ширину \(m\).

У наступних рядках міститься опис карти. При цьому . (крапка) означає, що в цьому квадраті немає вказівника, U — потрібно йти на північ, щоб вийти з села, D — потрібно йти на південь, L — на захід, R — на схід.

Місцезнаходження Андрія позначається на карті буквою M і у квадраті, в якому він стоїть, немає ніякого вказівника.

Початково Андрій прямує на схід.

Вихідні дані

Виведіть відстань (кількість квадратів), яку повинен пройти Андрій, поки не вибереться з села, або -1, якщо йому це не вдасться.

Обмеження

\(1 \le n, m \le 100\).

Приклади