永远不要以为 Matrix67 就是传说中的情圣。很少有人知道，Matrix67 竟然不好意思主动向 MM 表白！为此，Matrix67 派出他的表白机器人，帮他完成这一项光荣而艰巨的任务。
Matrix67 和 MM 所在的地方可以看作是一个封闭的平面空间，里面分成了 M x N 个房间，某些房间之间可能有墙。Matrix67 总在最左下角的那个房间，MM 总在最右上角的那个房间。Matrix67 需要给它的机器人输入一系列方向指令，控制机器人避开墙壁到达 MM 所在的位置。如果 L 表示向左移一格，R 表示向右移一格，U 表示向上移一格，D 表示向下移一格，那么在下图所示的 4x4 平面地图里，命令序列 RURUUR 可以让机器人从起点（左下角）到达终点（右上角）。
#---#---#---#---#
| | F |
# # # #---#
| | |
# # # #---#
| | |
# # # # #
| S |
#---#---#---#---#
但问题远远没有这么简单。由于设计上的缺陷，Matrix67 的机器人只能记忆 K 条指令。这就意味着，当机器人的行走路线过长时，指令不一定能完整地输入机器人。这怎么办呢？Matrix67 想到一个好办法：如果让机器人反复执行预先给定的 K 条指令，那么恰当的指令序列也能使机器人到达终点（虽然这样可能会走很多重复的路）。机器人会忽略所有命令它撞墙的指令。也就是说，如果下一个指令对应的方向上是一面墙的话，机器人将跳过该指令。Matrix67 希望知道，是否存在一个长度为 K 的命令序列，若机器人反复执行这段指令，最终会到达 MM 所在的地方。对于上面给出的例子，当 K=4 时，RRLU 是一个合法的答案。
【题目包含多组输入输出！】
输入格式
第一行输入四个用空格隔开的正整数 M、N、W 和 K，表示该平面区域内有 M 行 N 列小房间，房间与房间之间共有 W 面墙，Matrix67 需要给机器人输入的指令长度为 K。
以下 W 行每行四个数 Ai, Aj, Bi, Bj，表示第 Ai 行 Aj 列的房间与 Bi 行 Bj 列的房间之间有一面墙。
M,N<=5，K<=8。
输出格式
你的输出数据应该是一个由 L、R、U、D 四种字符组成的长度为 K 的字符串，表示一个合法的指令序列。机器人反复执行这串指令后最终可以到达右上角的房间。
输入数据保证有唯一解，因此你不用考虑多解或无解的情况。