The task about the magical hustle
Some rustling, like wings brushing against the walls, came from behind the hall. It was clear that an unheard-of crowd of guests was dancing there, and Margarita felt that even the massive marble, mosaic, and crystal floors in this strange hall were rhythmically pulsating.
"The Master and Margarita"
This intriguing story unfolded in a dream. Just imagine...
Sergey is dancing the hustle with a charming girl. The girl is wearing only a badge, which displays her name.
Suddenly, a couple of letters on the badge swap places... and then again... and again!
Sergey, sharp even in his sleep, discerns the pattern! The dance floor in the club is a rectangle of size n×n, where n is the length of the charming girl's name. Whenever Sergey and the girl step on a cell with coordinates (i, j), the letters at the i-th and j-th positions on her badge magically swap places.
Initially, Sergey and the girl are on the cell (i_1, j_1). The girl's badge displays the string s. Sergey dreams of reaching the cell (i_2, j_2), with the girl's badge showing the string t.
With each move, Sergey and the girl can step to an adjacent cell, either horizontally or vertically.
Input
The first line of the input contains the string s - the name of the charming girl at the start of Sergey's dream. The second line contains the numbers i_1 and j_1 - the initial coordinates of the dancing pair. The third line contains the string t - the name Sergey wishes to see on the girl's badge. The fourth line contains the numbers i_2 and j_2 - the coordinates of the cell where this should occur.
The girl's name consists only of uppercase and lowercase Latin letters, with uppercase and lowercase letters being distinct.
1 ≤ i_1, j_1, i_2, j_2 ≤ n = length(s) = length(t) ≤ 500.
Output
In the output, print the sequence of moves Sergey and the girl should make. The symbols "U" and "D" indicate decreasing and increasing the first coordinate by one, respectively, while "L" and "R" indicate decreasing and increasing the second coordinate by one, respectively.
If there are multiple solutions, print any one of them. The number of moves must not exceed 10^6 (Sergey must complete this before waking up). It is guaranteed that at least one solution exists (in a dream, all wishes come true).