Задача про чарівний хастл#5459
Якесь шурудіння, ніби крил стінами, доносилось тепер ззаду із зали, і було зрозуміло, що там танцюють нечувані натовпи гостей, і Маргариті здалося, що навіть масивні мармурові, мозаїчні та кришталеві підлоги у цьому дивному залі ритмічно пульсують.
"Майстер та Маргарита"
Ця повчальна історія трапилася у сні. Просто уявіть собі...
Сергій танцює хастл з чарівною дівчиною. На дівчині лише бейджик. На бейджику її ім'я.
Раптом на бейджику пара букв міняється місцями... і ще раз... і ще!
Сергій — розумний навіть у сні — обчислює закономірність! Виявляється, підлога у клубі являє собою прямокутник n \times n, де — це довжина імені чарівної дівчини, і як тільки Сергій та чарівна дівчина потрапляють на клітинку з координатами , у дівчини на бейджику тут же чарівним чином міняються місцями літери на -й та -й позиції.
Спочатку Сергій та чарівна дівчина перебувають на клітинці (i_1, j_1). На бейджику у дівчини рядок . Сергій мріє опинитися на клітинці (i_2, j_2), і щоб при цьому у чарівної дівчини на бейджику був рядок .
За один рух Сергій та чарівна дівчина можуть перейти на клітинку, суміжну по стороні з тією клітинкою, на якій вони зараз перебувають.
У першому рядку вхідного файлу міститься рядок — ім'я чарівної дівчини на початку сну Сергія. У другому рядку — числа i_1 та j_1 — координати танцюючої пари на початку сну. У третьому рядку — рядок — ім'я дівчини, яке хоче побачити Сергій. У четвертому рядку — числа i_2 та j_2 — координати клітинки, де це має відбутися.
В імені дівчини містяться лише великі і маленькі латинські літери. Великі і маленькі літери вважаються різними.
1 \leq i_1, j_1, i_2, j_2 \leq n = \text{length}(s) = \text{length}(t) \leq 500.
У вихідний файл виведіть послідовність рухів, які повинні здійснити Сергій та чарівна дівчина. Символи "U" та "D" позначають зменшення та збільшення на одиницю першої координати відповідно, а символи "L" та "R" — зменшення та збільшення другої координати відповідно.
Якщо розв'язків декілька, виведіть довільний із них. Кількість рухів не повинна перевищувати 10^6 (Сергій повинен встигнути до підйому). Гарантується, що хоча б один розв'язок існує (у сні всі бажання виконуються).
Приклад 1