I. Investigating Mars
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Nathalia, a software engineer and marathon enthusiast, is currently engaged with the MaratoNasa development team, working on the Mars exploration project. Her role is crucial in developing the software for the incredible exploratory robot K-IA-FFA.

The planet Mars is represented by a board with dimensions $$$n$$$ by $$$m$$$, where '$$$\#$$$' indicates a wall and '$$$.$$$' represents an empty space. Nathalia is currently in the testing stage of the final version of the K-IA-FFA software, which commands the movements of the exploratory robot. Her task is to evaluate the software's effectiveness in terms of board coverage.

The operation of the software follows a logical pattern:

  • If possible, the robot moves forward one square in the current direction.
  • Otherwise, it rotates $$$90^\circ$$$ counterclockwise and tries to move forward again.

It is important to note that the edges of the board are also considered walls to prevent the robot from escaping. Nathalia needs to calculate how many distinct squares on the board the robot will be able to visit in various possible scenarios.

Input

Each instance will represent a scenario. The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n, m \leq 10^3$$$) separated by a space, the dimensions of the board.

The next $$$n$$$ lines contain $$$m$$$ characters $$$a_{i, j} \in \{L, D, R, U, \cdot, \#\}$$$. The $$$L$$$ represents the initial position of the robot facing left, $$$R$$$ represents the initial position of the robot facing right, $$$D$$$ represents the initial position of the robot facing down, and $$$U$$$ represents the initial position of the robot facing up.

It is guaranteed that there is exactly one element from $$$\{L, D, R, U\}$$$ on the board and that this position is empty.

Output

The output must be a single integer $$$x$$$ which is the number of distinct squares of the board that K-IA-FFA will visit.

Examples
Input
2 2
.L
.#
Output
3
Input
2 2
L.
.#
Output
2
Input
4 4
#..#
#...
##.#
U..#
Output
9
Note

Consider the first example test case. The K-IA-FFA robot will follow these steps:

He will keep moving, but will not visit any new squares.