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