你可能玩过经典的电子游戏《青蛙过河》（Frogger）。在这个游戏中，青蛙必须穿过繁忙的街道，且不能被许多快速行驶的汽车撞到。随后，青蛙必须通过跳上浮木穿过河流，且不能掉进水里。

在本题中，我们关注游戏的第二部分，即青蛙利用浮木过河。游戏在一个矩形网格上进行。每根浮木的大小为一个网格方块。与真实游戏不同的是，浮木不仅可以水平漂浮，还可以垂直漂浮。

这意味着浮木之间也会发生碰撞。在这种情况下，多根浮木可以同时位于同一个网格方块上，它们会直接穿过彼此，而不会改变各自的方向和速度。当这种情况发生时，这是青蛙从一根浮木切换到另一根浮木的唯一时机。在任何时刻，青蛙总是位于某根浮木上，并随该浮木移动。如果在某一时刻，青蛙所在的浮木与另一根浮木位于同一个网格方块上，青蛙可以选择切换并继续在另一根浮木上移动。

输入描述了 $t = 0$ 时刻河流的状态。具体来说，输入定义了每根浮木的位置及其移动方向，即向上（^）、向下（v）、向左（<）或向右（>）。保证在 $t = 0$ 时刻，网格的左上角有一根浮木，青蛙从这里出发。在每个时间步，所有的浮木都会同时以相同的速度向其指定方向移动一个网格方块。网格是循环的：当浮木到达网格边缘时，它的下一个位置将出现在网格的对面边缘。

确定青蛙到达网格右下角的最早时间，或者判断它是否永远无法到达。

输入格式

第一行包含两个空格分隔的整数 $2 \le R, C \le 50$，表示网格的行数和列数。接下来的 $R$ 行，每行包含 $C$ 个字符，字符为点（.）表示该网格方块上没有浮木，或者为 ^v<> 中的一个，表示一根浮木及其移动方向。

输出格式

输出一行，包含青蛙到达网格右下角所需的最少时间步数；如果永远无法到达右下角，则输出 -1。

样例

样例输入 1

3 5
>^..v
...<.
.v..^

样例输出 1

5

样例输入 2

3 5
<....
.v...
...>.

样例输出 2

31

样例输入 3

2 2
><
><

样例输出 3

-1

说明

在第一个样例中，青蛙可以通过右-下-左-左-下的路径到达右下角。