Problem A
A New Adventure

‘Hunter’: a licensed profession for those who specialize in finding rare creatures or secret treasures.

Gon has embarked on a new journey to become a Hunter. Yesterday, Gon arrived in Hanoi to participate in the Hunter Exam — an annual exam which an applicant must pass, in order to become a Hunter.

The Hunter Examination Hall is surrounded by a circular road. We can model the road as $C$ concentric circles, numbered from $1$ to $C$ from the outermost circle to the innermost circle. The circles are each divided into $A$ arcs, numbered from $1$ to $A$ in clockwise order. The $j$-th arc in the $i$-th circle is denoted by $(i, j)$. Gon is currently standing at arc $(1, 1)$. The following image contains a circular road with $C = 3$ and $A = 8$.

There are motorbikes on the road. There is at most one motorbike in each arc, and there is no motorbike in arc $(1, 1)$. In the above image, there are $2$ motorbikes, one at arc $(1, 2)$ and another at arc $(2, 7)$.

All the motorbikes are travelling at constant speed of $1$ arc per second, in clockwise direction, without stopping. More precisely, if at second $T$, a motorbike is at $(i, j)$, then at second $T+1$, the motorbike will be at $(i, j \bmod A + 1)$.

Gon needs to go to the Examination Hall located inside the $C$-th circle. At each second, Gon can either stay at his current position, or move to an adjacent arc. Two arcs are adjacent if they share at least two points. From any arcs in the $C$-th circle, Gon can move to the Examination Hall.

Because Gon moves slightly faster than any motorbikes:

• If Gon moves from cell $(u, v)$ to cell $(x, y)$:

  • Gon will not be hit by motorbikes coming into cell $(u, v)$.

  • Gon will be hit by motorbikes coming from or into cell $(x, y)$.

• If Gon stays at cell $(u, v)$, he will be hit by motorbikes coming into cell $(u, v)$.

For example, in the above illustration, Gon can move as follows:

• At second $1$: Gon moves to arc $(2, 1)$, the $2$ motorbikes move to arc $(1, 3)$ and arc $(2, 8)$.

• At second $2$: Gon moves to arc $(3, 1)$, the $2$ motorbikes move to arc $(1, 4)$ and arc $(2, 1)$.

• At second $3$: Gon moves to Examination Hall, the $2$ motorbikes move to arc $(1, 5)$ and arc $(2, 2)$.

Note that:

• If at second $1$, Gon moves to arc $(1, 2)$, he will be hit by the motorbike moving from arc $(1, 2)$ to arc $(1, 3)$.

• If at second $2$, Gon stays at arc $(2, 1)$, he will also be hit by the motorbike moving from arc $(2, 8)$ to arc $(2, 1)$.

The Hunter Exam is starting soon, and Gon has not figured out how to cross the road yet. Please help him.

Input

The first line contains exactly $2$ positive integers $C$ and $A$. $(1 \le C \cdot A \le 10^5)$.

$C$ lines follow, the $i$-th line contains exactly $A$ characters representing the $i$-th circle. The $j$-th character in the $i$-th line can be either ‘G’, ‘M’ or ‘.’, representing the arc where Gon stands, an arc with a motorbike, or an empty arc, respectively.

The first character of the first line is always ‘G’, and this is the only ‘G’ in the input.

Output

Print exactly one integer — the minimum time for Gon to reach the Examination Hall. If it is impossible for Gon to reach the Examination Hall, print $-1$.

3 8
GM......
......M.
........

3