Mirko 厌倦了看书，所以他决定和朋友们一起去游乐园，尽管他并不喜欢过山车。当他的朋友们在尽情享受过山车的乐趣时，Mirko 正坐在长椅上，一边等待一边思考过山车可能的行驶路径。

游乐园的区域可以表示为一个 $R$ 行 $C$ 列的表格。过山车必须从表格的左上角出发，并在右下角结束。每个格子最多只能被访问一次，但不需要访问所有的格子。过山车可以从当前格子移动到其上方、下方、左侧或右侧相邻的格子。

每个格子都有一个与之关联的正整数，表示该格子对游客的趣味值。过山车的总趣味值是过山车访问的所有格子的趣味值之和。帮助 Mirko 确定一条趣味值最大的过山车路径（即总和最大的路径之一）。

输入格式

输入的第一行包含两个整数 $R$ 和 $C$（$2 \le R, C \le 1000$），表示表格的维度。

接下来的 $R$ 行，每行包含 $C$ 个小于 1000 的正整数，表示对应表格格子的趣味值。

输出格式

输出的第一行也是唯一的一行，必须包含一个不带空格的字母序列。这些字母指定了过山车所遵循的方向序列，从左上角开始，到右下角结束。上、右、下、左四个方向分别用字母 'U'、'R'、'D'、'L' 表示。

注意：不保证解是唯一的。

子任务

对于占总分 70% 的测试数据，满足 $R$ 和 $C$ 不超过 30。

样例

输入样例 1

3 3 
5 1 3 
2 4 8 
1 1 2

输出样例 1

RRDLLDRR

输入样例 2

2 2 
2 1 
3 4

输出样例 2

DR