Задача A. Дед Мазай и зайцы ≡

Условие

Дед Мазай давно живёт в деревне Малые Вежи. Так давно, что он составил карту высот окрестностей.

Карта представляет собой прямоугольник n × m клеток (n клеток в высоту и m клеток в ширину). Для клетки, находящейся в i-ом ряду на j-ой колонке, отмечена высота h_i,j местности в этой клетке над уровнем реки (в метрах). Известно, что для всех i выполняется соотношение h_i,1 = 0. То есть, изначально рекой затоплены те и только те клетки, которые располагаются в самом левом столбце карты.

На реке начался паводок. Уровень реки поднимается на 1 метр каждую минуту, затопляя окрестности. А именно, если клетка (i, j) соседствует с клеткой, затопленой рекой, и уровень реки уже достиг или превысил h_i,j, то считается, что клетка (i, j) также затоплена рекой. Клетки считаются соседними, если у них имеется одна общая сторона.

В начале паводка дед Мазай в своей лодке находится в клетке (1; 1) — в левом верхнем углу карты. За одну минуту дед Мазай может перебраться на соседнюю клетку, если она уже затоплена рекой или будет затоплена рекой к моменту окончания перехода.

Зайцы в начале паводка располагаются в клетке (i_r, j_r), j_r > 1. Обычно зайцы стоят на месте, но если на следующей минуте их клетка окажется затоплена рекой, то они пытаются перейти на соседнюю клетку, которая не будет затоплена рекой. Если таких клеток несколько, то они выбирают из них первую в следующем списке: верхняя, правая, нижняя, левая. Если соседних клеток, которые на следующей минуте не будут затоплены рекой, не существует, то зайцы утонут.

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

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

Зайцы никогда не выходят за пределы карты. Деду Мазаю также не разрешается выводить свою лодку за пределы карты.

В первом примере дед Мазай подплывает к зайцам через 4 минуты. Уровень реки в этот момент равен 4 метрам, и в следующую минуту река затопит всю местность. Зайцы оказываются спасены.

Во втором примере дед Мазай перемещается на одну клетку вправо и ждёт пока зайцы сами окажутся рядом с ним, спасаясь от потопа.

Во третьем примере, спасаясь от потопа, зайцы убегают в направлении от деда Мазая. Как бы дед Мазай ни действовал, он не успевает спасти зайцев.

Формат входного файла

В начале входного файла записаны целые числа n, m, i_r, j_r. Далее следует nm целых чисел h_i,j — карта.

Формат выходного файла

Если зайцев можно спасти, то выведите строку с инструкциями для деда Мазая. Каждый символ строки обозначает, что должен делать дед Мазай в очередную минуту:

• S — остаться на месте;
• U — сдвинутся на одну клетку вверх;
• R — сдвинутся на одну клетку вправо;
• D — сдвинутся на одну клетку вниз;
• L — сдвинутся на одну клетку влево.

Если зайцев спасти невозможно, выведите единственное слово "NO".

Ограничения

1 ≤ n, m ≤ 500;

1 ≤ i_r ≤ n;

2 ≤ j_r ≤ m;

1 ≤ h_i,j ≤ 10⁵ при j > 2;

h_i,1 = 0;

Примеры тестов

3 3 2 3
0 5 5
0 5 5
0 1 1

DDRR

5 4 5 2
0 1 1 1
0 4 5 6
0 3 1 1
0 2 1 1
0 1 1 1

RSS

4 2 2 2
0 1
0 1
0 2
0 3

NO