有一个被划分为 H 行 W 列的网格状场地。  

从北侧（上方）数第 i 行，从西侧（左侧）数第 j 列的格子用字符 A_{i,j} 表示。各字符的含义如下：

- `.` ：空格，可以进入。

- `#` ：障碍物，不能进入。

- `>`、`v`、`<`、`^` ：分别表示有一个人面朝东、南、西、北站在该格子，不能进入。人的视线宽度为 1 格，会沿着其面朝的方向笔直延伸，直到被障碍物或其他人阻挡为止。（也请参考输入输出样例 1 的说明。）

- `S` ：起点，可以进入。恰好只出现一次。保证不在任何人的视线范围内。

- `G` ：终点，可以进入。恰好只出现一次。保证不在任何人的视线范围内。

小z站在起点，可以任意多次向东西南北四个方向移动一格。但不能移动到不可进入的格子，也不能移出场地外。  

请判断他是否能在不进入任何人的视线范围的情况下到达终点。如果可以，请求出所需的最小移动次数。

第一行两个数字H,W表示地图的长和宽；

接下来H,W行列个字符，字符含义如上所示；

如果小z能够在不进入任何人的视线范围的情况下到达终点，请输出所需的最小移动次数。如果无法到达，请输出 `-1`。

30%的数据保证：2 \leq H, W \leq 20；

60%的数据保证：2 \leq H, W \leq 200；

100%的数据保证：2 \leq H, W \leq 2000；

- A_{i,j} 只会是 `.`, `#`, `>`, `v`, `<`, `^`, `S`, `G` 这几种字符之一

- `S` 和 `G` 在 A_{i,j} 中各出现且仅出现一次

- 起点和终点都保证不在任何人的视线范围内

 样例解释 1

对于输入样例 1，如果用 `!` 表示被至少一个人的视线覆盖的空格，场地如下图所示。  

对部分格子具体说明如下（这里用 (i, j) 表示北侧第 i 行、西侧第 j 列的格子）：

- (2, 4) 被 (2, 2) 处面朝东的人视线覆盖。

- (2, 6) 被 (2, 2) 处面朝东的人和 (1, 6) 处面朝南的两个人的视线覆盖。

- (4, 5) 没有被任何人的视线覆盖。(4, 7) 处面朝西的人的视线被 (4, 6) 的障碍物阻挡，(4, 1) 处面朝东的人的视线被 (4, 4) 的人阻挡。

小z必须避开不可进入的格子和被视线覆盖的格子，才能到达终点。

样例解释 2

如果小z无法到达终点，请输出 `-1`。