Робот находится на клетчатой прямоугольной доске размера \(n \times m\) (\(n\) строк, \(m\) столбцов). Строки пронумерованы от \(1\) до \(n\) сверху вниз, столбцы — от \(1\) до \(m\) слева направо.
Робот умеет передвигаться из текущей клетки в одну из четырех соседних с ней по стороне.
На каждой клетке доски написан один из символов 'L', 'R', 'D' или 'U', обозначающий направление движения робота, находящегося в этой клетке — влево, вправо, вниз или вверх, соответственно.
Начать свое движение робот может в любой клетке. После этого он за один ход перемещается в соседнюю по стороне клетку в направлении, указанном на текущей клетке.
- Если робот перемещается за границу доски, он падает и ломается.
- Если робот оказывается в клетке, в которой он был ранее, то он ломается (он останавливается и больше не двигается).
Робот может выбрать любую клетку в качестве стартовой. Его цель — совершить максимальное количество команд до поломки или остановки.
Определите, с какой клетки роботу стоит начинать свое движение, чтобы выполнить как можно больше команд. Команда считается успешно выполненной, если робот переместился с той клетки, на которой эта команда была написана (не важно, на другую клетку или за границу доски).
Выходные данные
Для каждого набора входных данных выведите три целых числа \(r\), \(c\) и \(d\) (\(1 \le r \le n\); \(1 \le c \le m\); \(d \ge 0\)), которые обозначают, что роботу следует начать движение из клетки \((r, c)\), чтобы сделать максимальное количество ходов \(d\). Если ответов несколько, то выведите любой из них.