题目描述

小明与红红在一个平面直角坐标系中进行抓人游戏。

初始小明在点 $A(x_1,y_1)$，红红在点 $B(x_2,y_2)$。小明待在原地不动等红红抓，红红希望走恰好 $k$ 步，并在 $k$ 步后到达小明的位置。

红红每一步有四种走法：

• L：从某个位置 $(x,y)$ 走到 $(x-1,y)$
• R：从某个位置 $(x,y)$ 走到 $(x+1,y)$
• U：从某个位置 $(x,y)$ 走到 $(x,y+1)$
• D：从某个位置 $(x,y)$ 走到 $(x,y-1)$

请你输出一个长度为 $k$ 的字符串，每个字符都是 L,R,U,D 之一。使得红红只要第 $i$ 步按照字符串的第 $i$ 个字符对应走法行走，就可以 $k$ 步后到达小明的位置。

如果无解输出 -1，如果有解输出任意一种方案即可。

输入格式

一行 $5$ 个数，分别为 $x_1,y_1,x_2,y_2,k$。

注意：变量名 y0,y1,yn,j0,j1,jn 在 <cmath> 中有定义，是贝塞尔函数的解，请避免在全局使用这些变量名。

输出格式

如果无解，输出 -1，否则输出一个长度为 $k$ 的字符串，为一种可行的走法。

1 1 1 2 9

URURDDLDL

样例解释 1

需要从 $B(1,2)$ 走 $9$ 步到达 $A(1,1)$。样例输出是一种走法，对应下图的路线。

1 1 1 1 2

LR

1 1 1 4 3

DDD

1 1 1 2 2

-1

1 1 1 3 1

-1

数据规模与约定

对于 $100\%$ 的数据，$-1000 \le x_1,y_1,x_2,y_2 \le 1000$，$1\le k\le 5000$。

• 子任务 1（30 分）：保证 $k=|x_1-x_2|+|y_1-y_2|$。
• 子任务 2（30 分）：保证 $x_1=x_2$。
• 子任务 3（40 分）：没有特殊限制。