Без лівих поворотів#3011
Людина в лабіринті повинна перейти з однієї клітини в іншу. За один хід вона може переміститися у суміжну клітину в одному з чотирьох напрямків (вгору, вниз, вліво або вправо), але існують певні обмеження. Початковий напрямок можна вибрати довільно. Однак після цього не дозволяється розвертатися на 180^\circ або робити повороти наліво (90^\circ проти годинникової стрілки). Таким чином, дозволені лише повороти на 90^\circ за годинниковою стрілкою. Також не дозволяється виходити за межі лабіринту.
Напишіть програму, яка знайде найкоротший допустимий шлях між заданими клітинами.
У першому рядку дано два цілі числа та (1 \leq M, N \leq 1500), розміри лабіринту. Далі йде рядків, кожен з яких містить символів, що описують лабіринт. Символ означає стіну (рух у цю клітину заборонений), — вільна клітина, — клітина старту, а — клітина призначення. Стартова та цільова клітини є вільними і зустрічаються у лабіринті по одному разу.
Виведіть в одному рядку найкоротшу послідовність ходів, яка переведе людину із стартової до цільової клітини, не роблячи поворотів на 180^\circ або вліво. Символ означає рух вгору, — вниз, — вліво, а — вправо. Якщо дістатися до цільової клітини із врахуванням обмежень неможливо, виведіть NO SOLUTION.
Приклад 1