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