410733: GYM104094 I Soviet Kindergarden

Mikhail Abramovich is a member of the CPSU since 1961, a doctor of sciences, a scientific atheist, loving dad and husband. He has a 10-year grandson Maxim. Maxim plays on his phone all day long instead of making science like his grandfather.

Maxim downloaded a new game "Snake 2022". The playing area of the "Snake 2022" is a rectangular table $$$n \times m$$$. Rows are enumerated from $$$1$$$ to $$$n$$$, columns are enumerated from $$$1$$$ to $$$m$$$. Cell $$$(r,c)$$$ is in the intersection of a row $$$r$$$ and a column $$$c$$$.

There is an apple in each cell of the table. When the head of the snake gets to the cell, the snake immediately eats an apple from this cell. The player gets $$$w_{ij}$$$ points when the snake eats an apple from the cell $$$(i,j)$$$.

The snake has a length of $$$1$$$ at the beginning of the game. The snake's head starts at cell $$$(a_r, a_c)$$$. The snake immediately eats an apple from a cell $$$(a_r, a_c)$$$. The game ends when the snake's head gets to the cell $$$(b_r, b_c)$$$.

The move in the game is moving the snake's head to any of the neighboring cells, in which there is no snake yet. On each move the snake eats an apple and increases its length by $$$1$$$. The set of cells occupied by the snake remains the same, plus the cell in which the snake's head appears in the current move. The move of the snake is described by one symbol: "U" to move up, from $$$(r, c)$$$ to $$$(r-1, c)$$$; "D" to move down, from $$$(r, c)$$$ to $$$(r+1, c)$$$; "L" to move left, from $$$(r, c)$$$ to $$$(r, c-1)$$$; "R" to move right, from $$$(r, c)$$$ to $$$(r, c+1)$$$.

Let $$$W$$$ be the total cost of apples on the whole table. The player wins if he gets strictly more than $$$\frac12 W$$$ points. To simplify the game, it is guaranteed that any apple brings strictly fewer points than the total cost of apples in cells $$$(a_r, a_c)$$$ and $$$(b_r, b_c)$$$.

"Snake 2022" is too difficult for Maxim, he can't win. He asked his grandfather for help. Mikhail Abramovich told Maxim the story of how in his youth the same problem was solved by an ordinary Soviet kindergartner.

You play the role of this kindergartner. Your task is to present a winning strategy for each configuration of the playing field from the tests.

The first line of the input contains a single integer $$$t$$$ — a number of the tests.

Each test is described in the following format. The first line contains six integers $$$n$$$, $$$m$$$, $$$a_r$$$, $$$a_c$$$, $$$b_r$$$, $$$b_c$$$ — the size of the table, coordinates of the start and finish cell ($$$2 \leq n, m \leq 5000$$$, $$$1 \leq a_r, b_r \leq n$$$, $$$1 \leq a_c, b_c \leq m$$$, the start and the finish cells are different). The sum $$$n \cdot m$$$ for all tests in one set of input data does not exceed $$$10^6$$$.

The next $$$n$$$ lines contain the costs of the apples in the table cells. The line $$$i$$$ contains integers $$$w_{i1}, w_{i2}, \ldots , w_{im}$$$ ($$$1 \leq w_{ij} \leq 10^9$$$. It is guaranteed that for any $$$1 \leq i \leq n$$$ and $$$1 \leq j \leq m$$$ inequality $$$w_{ij} < w_{a_ra_c} + w_{b_rb_c}$$$ is satisfied).

Output a line containing symbols "U", "D", "L", "R" for each test case — the sequence of the snake's moves, in which its head starts in the cell $$$(a_r, a_c)$$$, ends in the cell $$$(b_r, b_c)$$$, does not visit cells already occupied by the snake, and gets more than $$$\frac12 W$$$ points.

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