地图有 $H$ 行 $W$ 列。字符 S 是起点，G 是终点，. 是通道，# 是墙，字符 >、<、^、v 是朝相应方向观察的守卫。守卫的视线沿直线延伸，遇到墙或另一个守卫时停止。

小珅不能进入墙、守卫所在格或被任一守卫看见的格子，每步只能走到上下左右相邻格。请输出从 S 到 G 的最少步数；若无法到达，输出 $-1$。

输入格式

第一行输入 $H,W$。

接下来 $H$ 行输入地图。

输出格式

输出最少步数，无法到达输出 -1。

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

-1

6 7
S......
.......
.......
...>...
.......
......G

-1

7 8
S.......
........
........
......#.
........
........
.......G

-1

数据范围与约定

• $2 \le H,W \le 2000$
• 恰有一个 S 和一个 G