Problem Statement

There is a grid with $H$ rows and $W$ columns. The cell in the $i$-th row from the top and the $j$-th column from the left is denoted by $( i,\space j ) $. The grid consists of . , # , S , and G, where . represents a passage cell, # a wall cell, S the start cell, and G the goal cell. Here, cell $(1, \space 1)$ is S and cell $(H, \space W)$ is G, and there are no other S or G cells.

Before starting, you may use each of the following two types of superpowers zero or more times.

• Choose two adjacent rows and insert a row of . between them.
• Choose two adjacent columns and insert a column of . between them.

For example, if the grid is

S . # 
. # # 
. # G 

and you use a superpower between the 2nd and 3rd rows, the grid changes as follows.

S . # 
. # # 
. . . 
. # G 

If you then further use a superpower between the 1st and 2nd columns, the grid changes as follows.

S . . #
. . # #
. . . .
. . # G

You can move from your current cell to a cell adjacent to it vertically or horizontally. However, you cannot move outside the grid or onto a wall cell.

Determine whether you can reach G from S in the grid after using the superpowers, and if you can, find the minimum number of moves.

Constraints

• $2 \le H \le 2 \times 10^3$
• $2 \le W \le 2 \times 10^3$
• $H,W$ are integers
• $C_{i,j}$ is one of .,#,S,G
• S appears only at $(1, \space 1)$ and G appears only at $(H, \space W)$, one cell each

Input

$H\ W$
$C_{1,1}C_{1,2}\ \ldots C_{1,W}$
$C_{2,1}C_{2,2}\ \ldots C_{2,W}$
$\vdots$
$C_{H,1}C_{H,2}\ \ldots C_{H,W}$

Output

If reachable, print the minimum number of moves; otherwise, print −1.

Sample

3 3
S.#
.##
.#G

5

2 2
S.
.G

2

5 4
S...
###.
....
.###
...G

8