F. Wormholes
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

As is well known, Alexander loves to travel through space. The space itself is a field of size $$$n$$$ by $$$m$$$ cells. Each cell can be of one of two types: the first type is the most common space cell, and the second type is a wormhole, which instantly moves from this cell to a neighboring one (up, right, down, and left). At the moment, Alexander wants to fly on his ship from cell $$$(1, 1)$$$ to cell $$$(n, m)$$$.

In one hour, he can fly to a neighboring cell (up, right, down, and left), and he can also remove a wormhole in any cell at any time. After this, the cell with the wormhole will become a regular space cell, but this procedure is very expensive, and Alexander does not want to waste resources unnecessarily, so he wants to remove the minimum number of such cells. Movement in wormholes is instantaneous, therefore it does not take time.

Also, if a wormhole leads beyond the space field, the spaceship will crash, which Alexander definitely does not want.

Help Alexander spend the minimum amount of money and reach cell $$$(n, m)$$$ in the minimum number of hours from cell $$$(1, 1)$$$.

Input

The first line contains two numbers $$$n$$$ and $$$m$$$ — the sizes of the space.

Then there are $$$n$$$ lines, each containing $$$m$$$ characters.

Each character is one of the following:

  • "." — if this cell is a regular space cell.
  • "U" — if this cell has a wormhole that moves the ship from this cell to the cell above it.
  • "R" — if this cell has a wormhole that moves the ship from this cell to the cell to the right of it.
  • "D" — if this cell has a wormhole that moves the ship from this cell to the cell below it.
  • "L" — if this cell has a wormhole that moves the ship from this cell to the cell to the left of it.

Cells $$$(1, 1)$$$ and $$$(n, m)$$$ will always be regular space cells.

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

Output

Output two numbers, the first being the minimum number of removed wormholes, and the second number being the number of hours spent on the path when removing the minimum number of wormholes.

Examples
Input
1 4
.RR.
Output
0 1
Input
2 3
.D.
.D.
Output
1 2
Input
5 5
.U...
.U.D.
.U.D.
.U.D.
...D.
Output
0 16