Задача №115277. Советские ясли
У Михаила Абрамовича, члена КПСС с 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} < 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