eolymp
bolt
Try our new interface for solving problems
Məsələlər

Задача о волшебном хастле

Задача о волшебном хастле

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Какой-то шорох, как бы крыльев по стенам, доносился теперь сзади из залы, и было понятно, что там танцуют неслыханные полчища гостей, и Маргарите казалось, что даже массивные мраморные, мозаичные и хрустальные полы в этом диковинном зале ритмично пульсируют.

"Мастер и Маргарита"

Эта поучительная история произошла во сне. Просто представьте себе...

Сережа танцует хастл с очаровательной девушкой. На девушке только бейджик. На бейджике ее имя.

Внезапно на бейджике пара букв меняется местами... и еще раз... и еще!

Сережа - умный даже во сне - вычисляет закономерность! Оказывается, пол в клубе представляет собой прямоугольник n×n, где n - это длина имени очаровательной девушки, и как только Сережа и очаровательная девушка попадают на клетку с координатами (i, j), у девушки на бейджике тут же магическим образом меняются местами буквы на i-й и j-й позиции.

В начале Сережа и очаровательная девушка находятся на клетке (i_1, j_1). На бейджике у девушки строка s. Сережа мечтает оказаться на клетке (i_2, j_2), чтобы при этом у очаровательной девушки на бейджике красовалась строка t.

За одно движение Сережа и очаровательная девушка могут перейти на клетку, соседнюю по стороне с той клеткой, на которой они сейчас находятся.

Giriş verilənləri

В первой строке входного файла содержится строка s - имя очаровательной девушки в начале сережиного сна. Во второй строке - числа i_1 и j_1 - координаты танцующей пары в начале сна. В третьей строке - строка t - имя девушки, которое хочет увидеть Сережа. В четвертой строке - числа i_2 и j_2 - координаты клетки, на которой это должно произойти.

В имени девушки содержатся только заглавные и строчные латинские буквы. Заглавные и строчные буквы считаются различными.

1i_1, j_1, i_2, j_2n = length(s) = length(t)500.

Çıxış verilənləri

В выходной файл выведите последовательность движений, которые должны совершить Сережа и очаровательная девушка. Символы "U" и "D" обозначают уменьшение и увеличение на единицу первой координаты соответственно, а символы "L" и "R" - уменьшение и увеличение второй координаты соответственно.

Если решений несколько, выведите любое из них. Количество движений не должно превышать 10^6 (Сережа должен успеть до подъема). Гарантируется, что хотя бы одно решение существует (во сне все желания исполняются).

Nümunə

Giriş verilənləri #1
satanah
2 5
natasha
1 6
Çıxış verilənləri #1
ULLLLDUDRDUDRULDUDRDUDRDUDRDUDRULULULDUDRDUDRDUDRDUDRULULULDUDRDUDRULDUDRDUDRULDUDRUDULUDULUDULUDULUDULUDULRDUDRDUDRDUDRDUDRDUDRDUDLUDURDLUDULUDURDRDLUDULUDULUDURDRDLUDULUDULUDURDRDRDRDLUDULUDULUDULUDULUDURDLUDULUDURRRRR
Müəllif Михаил Дворкин, Аким Кумок