问题描述

A和B分别居住在一个$N \times M$的矩形网格区域中。每个网格可以是道路、墙壁或者房子。该地区因为道路复杂而蜿蜒曲折，所以经常发生痴汉事件而闻名，因此该地区与外部完全由墙壁包围并隔离。

B突然心血来潮，决定去看望A的家。然而，不幸的是，B看起来非常可疑，因此只要在去A家的路上有任何痴汉的嫌疑，他就会立即被逮捕。特别是绝对不能让右手离开墙壁。B是否可以不松开右手而一直到达A的家？

B始终面朝上下左右中的一个方向，并且B的右手可以触及的范围仅限于正前方、右前方、右侧和右后方的4个单元格。B可以执行以下操作之一，但不能同时执行这些操作：

• 如果前方没有墙壁，则向前移动1个单元格。
• 将面对的方向旋转90度向右。
• 将面对的方向旋转90度向左。
• 更换右手接触的单元格。不过，在这种情况下，B不能松开右手，所以更改前后的单元格必须有一个共同点。

输入

输入以以下格式给出:

$N$ $M$
$S\_1$
$S\_2$
:
:
$S\_N$

其中，$S\_i$ ($1 \le i \le N$) 是一个长度为$M$的字符串，每个字符表示如下：

• "^"，"v"，"<"，">"表示B最初所在的位置和面朝的方向（上下左右）。
• "." 表示没有什么，表示空单元格。B可以通过这个单元格移动。
• "#" 表示墙壁。B不能通过这个单元格移动。
• "G" 表示A的家的位置。B将一直移动直到到达A的家。

约束条件

• $1 \le N \le 50$
• $1 \le M \le 50$
• 输入中必定只有字符 "^"，"v"，"<"，">" 中的一个。
• 同样地，输入中必定只有一个字符 "G"。
• 在初始状态下，B的右手与B面对的方向的右侧墙壁接触。

输出

如果能够到达A的家而不松开右手，则输出到达A的家之前经过的不同单元格数量的最小值。如果无法到达A的家，则输出-1。

样例输入1

3 3
G##
.#.
.<.```

### 对应输出1

```plain
4```

### 样例输入2

```plain
3 3
G##
.#.
.>.```

### 对应输出2

```plain
6```

### 样例输入3

```plain
3 3
...
.G.
.>.```

### 对应输出3

```plain
-1```

### 样例输入4

```plain
4 4
....
.#.G
...#
^#..```

### 对应输出4

```plain
8```