Squid Ink

Problem

近年、イカたちの間では縄張り争いが頻繁に起きている。複数のイカたちがチームを組み、自らのイカスミを武器に戦うのが近年のイカの戦闘スタイルである。

現在も縄張り争いが起こっており、その戦場は R×C のグリッドで表される。縄張り争いに参加しているイカのゲソ太はこのグリッド上のある場所にいる。この争いでは、重要な場所を敵よりも早く占拠することで戦況を有利にすることができる。そのため、ゲソ太は重要そうな場所を1つ決め、そこになるべく早く移動したいと考えている。

ゲソ太は隣接する上下左右のマスに移動することができる。グリッドの各マスには味方、または敵のイカスミが塗られている場合がある。なにも塗られていないマスに移動する場合、2秒かかるが、味方のイカスミが塗られているマスに移動する場合、その半分の時間(1秒)で済む。敵のイカスミが塗られているマスには移動することができない。壁があるマスや戦場の外へは当然移動することができない。

また、ゲソ太は上下左右のいずれかの方向を向き、イカスミを吐くことができる。すると、前方の3マスが味方のイカスミで上書きされる。ただし途中に壁がある場合はその手前までしかイカスミは届かない。この動作には2秒かかる。

戦場の情報とゲソ太の位置と目的の位置が与えられるので、最短で何秒で移動できるか求めてほしい。

Input

入力は以下の形式で与えられる。

R C
a1,1 a1,2 ... a1,C
a2,1 a2,2 ... a2,C
:
aR,1 aR,2 ... aR,C

1行目に2つの整数R,Cが空白区切りで与えられる。続くR行に戦場の情報としてC個のマスの情報が与えられる。a_i,jは戦場の位置(i,j)のマスの情報を表し、以下のいずれかの文字である。

• '.': なにも塗られていないマス
• '#': 壁
• 'o': 味方のイカスミが塗られているマス
• 'x': 敵のイカスミが塗られているマス
• 'S': ゲソ太の位置(入力中に1つだけ存在し、マスはなにも塗られていない)
• 'G': 目的の位置(入力中に1つだけ存在し、マスはなにも塗られていない)

与えられる入力は、目的の位置まで移動することが可能であることが保証される。

Constraints

• 2 ≤ R,C ≤ 30

Output

ゲソ太が目的の位置まで移動するのにかかる最短の秒数を1行に出力せよ。

Sample Input 1

5 5
S....
.....
.....
.....
....G

Sample Output 1

14

Sample Input 2

5 5
Sxxxx
xxxxx
xxxxx
xxxxx
xxxxG

Sample Output 2

15

Sample Input 3

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

Sample Output 3

23

Sample Input 4

4 5
S#ooo
o#o#o
o#o#o
ooo#G

Sample Output 4

14

Sample Input 5

4 5
G####
ooxoo
##x#o
Soooo

Sample Output 5

10