Людині, яка знаходиться у деякому лабіринті, потрібно потрапити з однієї клітинки у іншу. Кожним ходом він може переміститись на одну клітинку у одному з чотирьох напрямків (угору, донизу, ліворуч або праворуч), проте є деякі обмеження на його переміщення. Початковий напрям руху він може вибрати довільний. Проте після цього не дозволяється повертатись на \textbf{180}° і робити ліві повороти (повороти на \textbf{90}° проти годинникової стрілки). Таким чином дозволені лише повороти на \textbf{90}° за годинниковою стрілкою. Крім того забороняється залишати межі лабіринту. Напишіть програму для знаходження найкоротшого дозволеного шляху між заданими клітинками. \InputFile У першому рядку задано два цілих числа \textbf{M} і \textbf{N} (\textbf{1} ≤ \textbf{M}, \textbf{N} ≤ \textbf{1500}), які визначають розміри лабіринту. Далі йде \textbf{M} рядків по \textbf{N} символів у кожному, які описують лабіринт. Символ "\textbf{*}" позначає стіну (у відповідну клітинку не дозволяється рухатись), "\textbf{.}" - вільна клітинка, "\textbf{S}" - клітинка, де спочатку знаходиться людина, "\textbf{D}" - клітинка, куди потрібно дістатись. Початкова і кінцева клітинка вважаються вільними і зустрічаються рівно по одному разу. \OutputFile У єдиний рядок виведіть рядок, який визначає найкоротшу послідовність ходів, яка зможе привести людину з початкової клітинки у кінцеву без розворотів та лівих поворотів. Символ "\textbf{U}" цього рядкаи позначає переміщення угору на одну клітинку, "\textbf{D}" - донизу, "\textbf{L}" - ліворуч, "\textbf{R}" - праворуч. Якщо дістатись до кінцевої клітинки без порушень правил неможливо, виведіть повідомлення "\textbf{NO SOLUTION}" (без лапок).