100512: [AtCoder]ABC051 C - Back and Forth

Problem Statement

Dolphin resides in two-dimensional Cartesian plane, with the positive $x$-axis pointing right and the positive $y$-axis pointing up.
Currently, he is located at the point $(sx,sy)$. In each second, he can move up, down, left or right by a distance of $1$.
Here, both the $x$- and $y$-coordinates before and after each movement must be integers.
He will first visit the point $(tx,ty)$ where $sx < tx$ and $sy < ty$, then go back to the point $(sx,sy)$, then visit the point $(tx,ty)$ again, and lastly go back to the point $(sx,sy)$.
Here, during the whole travel, he is not allowed to pass through the same point more than once, except the points $(sx,sy)$ and $(tx,ty)$.
Under this condition, find a shortest path for him.

Constraints

• $-1000 ≤ sx < tx ≤ 1000$
• $-1000 ≤ sy < ty ≤ 1000$
• $sx,sy,tx$ and $ty$ are integers.

Input

The input is given from Standard Input in the following format:

$sx$ $sy$ $tx$ $ty$

Output

Print a string $S$ that represents a shortest path for Dolphin.
The $i$-th character in $S$ should correspond to his $i$-th movement.
The directions of the movements should be indicated by the following characters:

• U: Up
• D: Down
• L: Left
• R: Right

If there exist multiple shortest paths under the condition, print any of them.

Sample Input 1

0 0 1 2

Sample Output 1

UURDDLLUUURRDRDDDLLU

One possible shortest path is:

• Going from $(sx,sy)$ to $(tx,ty)$ for the first time: $(0,0)$ → $(0,1)$ → $(0,2)$ → $(1,2)$
• Going from $(tx,ty)$ to $(sx,sy)$ for the first time: $(1,2)$ → $(1,1)$ → $(1,0)$ → $(0,0)$
• Going from $(sx,sy)$ to $(tx,ty)$ for the second time: $(0,0)$ → $(-1,0)$ → $(-1,1)$ → $(-1,2)$ → $(-1,3)$ → $(0,3)$ → $(1,3)$ → $(1,2)$
• Going from $(tx,ty)$ to $(sx,sy)$ for the second time: $(1,2)$ → $(2,2)$ → $(2,1)$ → $(2,0)$ → $(2,-1)$ → $(1,-1)$ → $(0,-1)$ → $(0,0)$

Sample Input 2

-2 -2 1 1

Sample Output 2

UURRURRDDDLLDLLULUUURRURRDDDLLDL