弗拉达公主喜欢在草地上跳跃和在森林里散步。有一天——美好的、阳光明媚的一天——公主在散步时惊讶地发现她的影子不见了! “天哪!”——她想道,然后开始寻找森林里的影子。
通常情况下,影子太懒了,只是睡在公主下面。但在这个炎热的夏天,她厌倦了这样平淡的生活,所以她决定和弗拉达一起玩。
森林,我们的角色自娱自乐的地方,可以被表示为平面中的一组整数单元,其中影子和公主只能向上、向下、向左和向右移动 1。一些单元(就像在像样的森林中发生的那样)被树木占据。影子和公主不允许进入有树的牢房。不幸的是,现在正是森林的艰难时期,所以这里生长的树木很少......
起初,公主在牢房 (vx, vy) 内行走,而影子则躲在牢房 (sx, sy) 中躲避公主。公主、影子和树木位于不同的牢房中。
影子正在和公主玩耍。一旦公主向某个方向移动 1,如果可能的话,影子会同时向同一方向飞行 1(如果要飞向的单元格没有被某棵树占据);否则,影子就不会移动。阴影非常阴暗,所以我们的角色不会互相干扰。
如果经过一些移动后,影子和公主都位于同一个牢房中,我们就说影子被公主抓住了。弗拉达成功抓住了她的影子!你可以吗?
输入
输入的第一行包含字符 vx、vy、sx、sy 的坐标和树的数量 m (0 ≤ m ≤ 400)。接下来的 m 行包含树木的坐标。
所有坐标均为 -100 到 100 之间的整数(包含 -100 和 100)。公主、影子和树木位于不同的牢房中。
输出
如果公主不可能抓住影子,则打印“-1”(不带引号)。
否则打印一系列字符“L”,“R”,“D”,“U”,对应于公主的移动,随后她将能够在某个回合抓住影子(L - 向左移动,R - 向右,U - 向上,D - 向下;x 轴指向右侧,y - 向上)。
字符数(即步数)不得超过106个。公主的所有步法必须正确,即不能通向长有树的单元格。在最后一轮之前,公主和影子可以占据同一个牢房。
示例
输入 #1
0 0 1 0 1 0 1
输出 #1
LLUR
输入 #2
5 0 3 0 8 2 -1 2 0 2 1 3 -1 4 1 4 0 3 1 4 -1
输出 #2
-1
输入 #3
3 2 1 1 3 0 1 1 0 0 0
输出 #3
DLL
注意
下面给出了样本的图片(公主、影子和树木分别用粉红色、灰色和黑色着色;蓝点标记了格子中心)。
在第一种情况下,公主可以向左迈两步,向上迈一步,向右迈一步:
在以下情况下,公主无法捕捉到影子:
在最后一个示例中,公主可以向左迈两步,向下迈一步(以任何顺序):