题目描述

Maxim 在手机上玩新游戏“Snake 2022”。游戏区域是 $n\times m$ 的矩形网格。每个格子里都有一个苹果，蛇头到达某格时会立刻吃掉该格苹果，玩家获得该格的分数 $w_{ij}$。

游戏开始时蛇长度为 $1$，蛇头位于 $(a_r,a_c)$，并立即吃掉该格苹果。游戏在蛇头到达 $(b_r,b_c)$ 时结束。

一次移动是让蛇头移动到一个相邻且尚未被蛇占据的格子。每次移动后蛇吃掉新格子的苹果，长度增加 $1$，已占据格子不会消失。移动用字符表示：

• U：上移；
• D：下移；
• L：左移；
• R：右移。

设整张表所有苹果分数之和为 $W$。若玩家获得的分数严格大于 $\frac12 W$，则获胜。

为了简化问题，保证任意一个苹果的分数都严格小于起点和终点苹果分数之和。

请为每个测试用例输出一条获胜路径。

输入格式

第一行包含整数 $t$，表示测试组数。

每组测试第一行包含六个整数：

$$n,m,a_r,a_c,b_r,b_c,$$

其中：

$$2\le n,m\le 5000, \quad 1\le a_r,b_r\le n, \quad 1\le a_c,b_c\le m,$$

起点和终点不同。所有测试中 $n\cdot m$ 之和不超过 $10^6$。

接下来 $n$ 行，每行包含 $m$ 个整数 $w_{ij}$：

$$1\le w_{ij}\le 10^9.$$

并保证对任意格子 $(i,j)$ 都有：

$$w_{ij}<w_{a_r,a_c}+w_{b_r,b_c}.$$

输出格式

对每个测试用例输出一行由 U、D、L、R 组成的字符串，表示蛇的移动序列。

该序列必须满足：

• 从 $(a_r,a_c)$ 出发；
• 最终到达 $(b_r,b_c)$；
• 不访问已经被蛇占据的格子；
• 获得的总分严格大于 $\frac12 W$。

样例

2
2 2 1 1 2 2
1 9
1 9
2 4 1 2 2 3
2 1 5 6
3 4 8 7

RD
RRDL