I. Советские ясли
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Михаила Абрамовича, члена КПСС с 1961 года, доктора наук, научного атеиста, любящего мужа и отца, 10 лет назад родился внук по имени Максим. Но в отличие от своего дедушки Максим не увлекается науками, а вместо этого дни напролет играет в игры на телефоне.

Недавно Максим скачал себе новую игру на телефон — «Змейка 2022». Игровое поле для «Змейки 2022» представляет собой прямоугольную таблицу $$$n \times m$$$. Клеткой $$$(r,c)$$$ будем называть клетку, которая находится на пересечении $$$r$$$-й строки и $$$c$$$-го столбца, пронумеруем строки сверху вниз от $$$1$$$ до $$$n$$$, столбцы — слева направо от $$$1$$$ до $$$m$$$. В каждой клетке поля находится яблоко, которое змейка съедает, когда ее голова оказывается в этой клетке. При этом игрок получает $$$w_{ij}$$$ очков, когда змейка съедает яблоко, которое находится в клетке $$$(i,j)$$$.

В начале игры змейка имеет длину $$$1$$$, ее голова появляется в клетке $$$(a_r, a_c)$$$ и немедленно съедает расположенное там яблоко. Игра заканчивается, когда голова змейки оказывается в клетке $$$(b_r, b_c)$$$.

За один ход игрок перемещает голову змейки в любую из соседних клеток, которая пока не занята змейкой. Так как в каждой клетке находится яблоко, то змейка наращивает свою длину на $$$1$$$ после каждого хода и множество клеток, занятых змейкой остается тем же, плюс к нему добавляется клетка, в которую переместилась её голова. Ход змейки описывается одним символом: «U» для перемещения вверх, из $$$(r, c)$$$ в $$$(r-1, c)$$$; «D» для перемещения вниз, из $$$(r, c)$$$ в $$$(r+1, c)$$$; «L» для перемещения влево, из $$$(r, c)$$$ в $$$(r, c-1)$$$; «R» для перемещения вправо, из $$$(r, c)$$$ в $$$(r, c+1)$$$.

Пусть $$$W$$$ — суммарная стоимость яблок внутри поля, тогда считается, что игрок победил, если набрал строго больше $$$\frac12 W$$$ очков. При этом для упрощения игры гарантируется, что любое яблоко приносит строго меньше очков, чем суммарно приносят яблоки в клетках $$$(a_r, a_c)$$$ и $$$(b_r, b_c)$$$.

Для Максима данная игра оказалась слишком сложной, он никак не может выиграть. Поэтому он обратился за помощью к своему дедушке. Михаил Абрамович же в ответ рассказал историю, как во время его молодости точно такую же задачу решил обычный советский детсадовец.

Вы выступаете в роли этого детсадовца, ваша задача заключается в том, чтобы для каждой конфигурации игрового поля из тестов предъявить выигрышную стратегию.

Входные данные

В первой строке дано число $$$t$$$ — количество тестов во входных данных.

Каждый из тестов описывается в следующем формате. В первой строке указаны шесть чисел $$$n$$$, $$$m$$$, $$$a_r$$$, $$$a_c$$$, $$$b_r$$$, $$$b_c$$$ — размеры поля, координаты начальной клетки и координаты конечной клетки ($$$2 \leq n, m \leq 5000$$$, $$$1 \leq a_r, b_r \leq n$$$, $$$1 \leq a_c, b_c \leq m$$$, начальная и конечная клетки различны).

Сумма $$$n \cdot m$$$ по всем тестам в одном наборе входных данных не превышает $$$10^6$$$.

В следующих $$$n$$$ строках перечисляются стоимости яблок, находящихся в клетках поля, а именно, в $$$i$$$-й из этих строк содержатся целые числа $$$w_{i1}, w_{i2}, \ldots , w_{im}$$$ ($$$1 \leq w_{ij} \leq 10^9$$$, гарантируется что для любых $$$1 \leq i \leq n$$$ и $$$1 \leq j \leq m$$$ выполняется неравенство $$$w_{ij} \lt w_{a_ra_c} + w_{b_rb_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