Задача о волшебном хастле
Какой-то шорох, как бы крыльев по стенам, доносился теперь сзади из залы, и было понятно, что там танцуют неслыханные полчища гостей, и Маргарите казалось, что даже массивные мраморные, мозаичные и хрустальные полы в этом диковинном зале ритмично пульсируют.
"Мастер и Маргарита"
Эта поучительная история произошла во сне. Просто представьте себе...
Сережа танцует хастл с очаровательной девушкой. На девушке только бейджик. На бейджике ее имя.
Внезапно на бейджике пара букв меняется местами... и еще раз... и еще!
Сережа - умный даже во сне - вычисляет закономерность! Оказывается, пол в клубе представляет собой прямоугольник n×n, где n - это длина имени очаровательной девушки, и как только Сережа и очаровательная девушка попадают на клетку с координатами (i, j), у девушки на бейджике тут же магическим образом меняются местами буквы на i-й и j-й позиции.
В начале Сережа и очаровательная девушка находятся на клетке (i_1, j_1). На бейджике у девушки строка s. Сережа мечтает оказаться на клетке (i_2, j_2), чтобы при этом у очаровательной девушки на бейджике красовалась строка t.
За одно движение Сережа и очаровательная девушка могут перейти на клетку, соседнюю по стороне с той клеткой, на которой они сейчас находятся.
Входные данные
В первой строке входного файла содержится строка s - имя очаровательной девушки в начале сережиного сна. Во второй строке - числа i_1 и j_1 - координаты танцующей пары в начале сна. В третьей строке - строка t - имя девушки, которое хочет увидеть Сережа. В четвертой строке - числа i_2 и j_2 - координаты клетки, на которой это должно произойти.
В имени девушки содержатся только заглавные и строчные латинские буквы. Заглавные и строчные буквы считаются различными.
1 ≤ i_1, j_1, i_2, j_2 ≤ n = length(s) = length(t) ≤ 500.
Выходные данные
В выходной файл выведите последовательность движений, которые должны совершить Сережа и очаровательная девушка. Символы "U" и "D" обозначают уменьшение и увеличение на единицу первой координаты соответственно, а символы "L" и "R" - уменьшение и увеличение второй координаты соответственно.
Если решений несколько, выведите любое из них. Количество движений не должно превышать 10^6 (Сережа должен успеть до подъема). Гарантируется, что хотя бы одно решение существует (во сне все желания исполняются).