Teacher Mai 处于一个 $n$ 行 $m$ 列的迷宫中。每个单元格中都有一个非负整数。Teacher Mai 想要从左上角 $(1, 1)$ 走到右下角 $(n, m)$。他可以选择一个方向并走到相邻的单元格。然而，他不能走出迷宫，且不能重复访问同一个单元格。

Teacher Mai 想要最大化他路径上数字的和，你需要输出这条路径。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 130$)，表示测试用例的数量。

对于每个测试用例，第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 100, n \cdot m \ge 2$)。

接下来的 $n$ 行，每行包含 $m$ 个数字。第 $i$ 行的第 $j$ 个数字表示单元格 $(i, j)$ 中的数字。每个单元格中的数字不超过 $10^4$。

输出格式

对于每个测试用例，第一行输出最大和。

下一行输出一个由 'L'、'R'、'U' 和 'D' 组成的字符串，表示你找到的路径。如果你在单元格 $(x, y)$，'L' 表示你走到单元格 $(x, y-1)$，'R' 表示你走到单元格 $(x, y+1)$，'U' 表示你走到单元格 $(x-1, y)$，'D' 表示你走到单元格 $(x+1, y)$。

样例

输入 1

1
3 3
2 3 3
3 3 3
3 3 2

输出 1

25
RRDLLDRR