F. Кротовые норы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Как всем известно, Александр любит путешествовать по космосу. Сам космос представляет из себя поле размером $$$n$$$ на $$$m$$$ клеток. Каждая клетка бывает одного из двух видов: первый вид — это самая обычная клетка космоса, второй вид — это кротовая нора, которая моментально перемещает из этой клетки в соседнюю (вверх, вправо, вниз и влево). В данный момент Александр хочет полететь на своем корабле из клетки $$$(1, 1)$$$ в клетку $$$(n, m)$$$.

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

Также если кротовая нора ведет за пределы поля космоса, то космический корабль разобьется, чего Александр совсем не хочет.

Помогите Александру потратить минимальное количество денег и за минимальное количество часов попасть из клетки $$$(1, 1)$$$ в клетку $$$(n, m)$$$.

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

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

Далее идет $$$n$$$ строк, в каждой из которых содержится по $$$m$$$ символов.

Каждый символ является одним из ниже перечисленных:

  • «.» — если эта клетка является обычной клеткой космоса.
  • «U» — если эта клетка с кротовой норой, которая переносит корабль из данной клетки в клетку выше данной.
  • «R» — если эта клетка с кротовой норой, которая переносит корабль из данной клетки в клетку правее данной.
  • «D» — если эта клетка с кротовой норой, которая переносит корабль из данной клетки в клетку ниже данной.
  • «L» — если эта клетка с кротовой норой, которая переносит корабль из данной клетки в клетку левее данной.

Клетка $$$(1, 1)$$$ и $$$(n, m)$$$ всегда будут обычными клетками космоса.

$$$$$$1 \le n \le 10^5$$$$$$ $$$$$$1 \le m \le 10^5$$$$$$ $$$$$$1 \le n \cdot m \le 10^6$$$$$$

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

Выведите два числа, первое является минимальное количество удаленных кротовых нор, а второе число является количеством затраченных часов на путь при уничтожении минимального количества кротовых нор.

Примеры
Входные данные
1 4
.RR.
Выходные данные
0 1
Входные данные
2 3
.D.
.D.
Выходные данные
1 2
Входные данные
5 5
.U...
.U.D.
.U.D.
.U.D.
...D.
Выходные данные
0 16