Робот находится в левой верхней клетке прямоугольной сетки размером m x n. В каждой клетке лежит некоторое неотрицательное число монет.

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

Требуется вывести любой путь, на котором робот соберёт максимальное возможное количество монет. Путь должен быть записан в виде строки из символов R и D длины m + n - 2.

Если m = 1 и n = 1, путь пустой.

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

В первой строке даны два целых числа m и n — размеры сетки.

В следующих m строках содержится по n целых чисел a_ij, где a_ij — количество монет в клетке, расположенной в i-й строке и j-м столбце.

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

Выведите одну строку из символов R и D — любой путь из левой верхней клетки в правую нижнюю, на котором собирается максимальное количество монет.

Если путь пустой, выведите пустую строку.

Ограничения

• 1 <= m, n <= 1000
• 0 <= a_ij <= 10^9

Примеры

Пример 1

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

3 3
1 3 1
1 5 1
4 2 1

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

RDDR

Пояснение

Путь RDDR проходит клетки 1, 3, 5, 2, 1 и собирает 12 монет — это максимум. Подойдёт любой оптимальный путь.

Пример 2

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

1 1
0

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

Пример 3

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

1 2
0 0

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

R