Представим себе бесконечное клетчатое поле, в каждой клетке стоит 0. Однако клетки в прямоугольнике N × M, левая верхняя клетка которого имеет координату (1, 1), правая нижняя — (N, M), имеют своё значение a_ij.

В клетке (1, 1) стоит робот, которому дана программа S. Эта программа состоит из 4-х различных команд-символов:

• ‘R’ — робот движется вправо, то есть из клетки (x, y) робот переместится в клетку (x, y+1);
• ‘D’ — робот движется вниз, то есть из клетки (x, y) робот переместится в клетку (x+1, y);
• ‘L’ — робот движется влево, то есть из клетки (x, y) робот переместится в клетку (x, y−1);
• ‘U’ — робот движется вверх, то есть из клетки (x, y) робот переместится в клетку (x−1, y).

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

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

В первой строке даны два целых числа N и M — размеры прямоугольника (1 ≤ N, M ≤ 10⁵, N · M ≤ 10⁵).

В следующих N строках даётся по M целых чисел a_ij — значение в клетке (i, j) (|a_ij| ≤ 10⁹).

В последней строке описана программа S, состоящая из символов ‘R’, ‘D’, ‘L’ и ‘U’ (2 ≤ |S| ≤ 10⁵).

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