Problem D. Deft ninja ≡

Statement

Ninja wants to gain an artifact located in the field of size N ⋅ M.

There are guards in the field. Each of them is looking in one direction and turns clockwise in the end of each second, so after four seconds a guard makes full rotation. A guard raises the alarm if he sees the ninja located on the line of guards sight, and nobody is located between them. The artifact is too small and doesn't obstruct guards sight.

Initially the ninja is located in the cell marked 'N', the artifact is in the cell marked 'A', guards are located in the cells marked '>', '<', '^', 'v' accordingly to their initial sight direction. In the end of each second ninja can move one cell in any of four direction or stay in the same place.

It is guaranteed that in the cell with guard there are no ninja, artifact or another guard. Initially (during the zero second) none of guards can see the ninja.

Your task is to find the minimal number of seconds the ninja needs to reach the artifact without being noticed or tell, that it's impossible.

Input format

The first line contains two integers N and M — field size. Then follow N strings of M symbols describing the field.

Output format

Print one integer — the minimal number of seconds the ninja needs to reach the artifact without being noticed, or "-1" if it's impossible.

Constraints

2 ≤ N, M ≤ 1000

Sample tests

2 2
A>
.N

3

3 3
A.<
<.v
^Nv

-1

4 4
.^..
<A.v
..N.
.<..

4

5 5
A...<
.....
....v
...N.
>^<v.

9