Description

The territory of Country I is an $n \times m$ rectangle, and each cell has its own wind direction.

When a paratrooper is at some cell, according to the wind direction descriptor on that cell, the following will happen:

We assume that all cells outside Country I’s territory have the wind descriptor x.

Now, the commander drops one paratrooper on each of the $n \times m$ cells. How many paratroopers will eventually land successfully (that is, can reach a cell with descriptor o after a finite number of moves)?

Input Format

The first line contains two positive integers $n, m\ (1 \leq n, m \leq 1000)$.

The next $n$ lines each contain $m$ characters, representing the wind descriptor of each cell.

It is guaranteed that only u/d/l/r/o appear in the input; x does not appear.

Output Format

A single integer: the number of paratroopers that can land successfully.

5 5
rrrrr
rdddr
rroll
uuuuu
uuuuu

19

Hint

Explanation of the sample:

The $5$ paratroopers dropped in the first row will eventually move outside Country I’s territory, thus failing to land.

The one paratrooper dropped in the second row, fifth column will do the same.

The remaining $5 \times 5-5-1=19$ paratroopers will all land successfully.

Translated by ChatGPT 5