When two sets of eyes meet,

問題文

とある世界では、「魔物使い同士の目が合ったら、その場でお互いの連れているモンスターを戦わせなければならない。」という掟があるんだとか。

魔物使いであるmoguさんは、冒険の途中で連れているモンスターが傷を負ってしまったので、近くの町の宿へ行って休ませたいと考えている。しかし、町への道中には冒険中の魔物使いがいるため、できるだけ彼らと目を合わせないようにしたい。

$H$ 行 $W$ 列のグリッドがあり、$i$ 行 $j$ 列 のマスを マス $(i,j)$ と定める。また、$i$ が小さくなる方向を 北 、$i$ が大きくなる方向を 南 、$j$ が小さくなる方向を 西 、$j$ が大きくなる方向を 東 と定める。

moguさんは今、マス $(1,1)$ におり、町は マス $(H,W)$ にある。 冒険中の魔物使いは このグリッド内に $N$ 人おり、魔物使い $j(1 \leq i \leq N)$ は $S_{r_i,c_i} =$ ^ のとき北を、$S_{r_i,c_i} =$ v のとき南を、$S_{r_i,c_i} =$ < のとき西を、$S_{r_i,c_i} =$ > のとき東を向いている。

はじめ、moguさんはどの魔物使いとも戦闘していない。moguさんが魔物使いの向く方向にいたとき、moguさんとその魔物使いで戦闘が発生する。該当する魔法使いが複数いる場合、その全員とそれぞれ戦闘が発生するものとする。ただし、moguさんと戦闘したことのある魔物使いとの再戦が発生することはない。

moguさんと魔物使いが同じグリッド内にいることはできないものとする。moguさんが上下左右のマスへの移動を繰り返すことで町へ向かう際の、戦闘回数の最小値を求めよ。

制約

• $3 \leq H,W$
• $HW \leq 1000$
• $1 \leq N \leq 10$
• $S_{i,j} =$ . , ^ , v , < , > $(1 \leq i \leq H , 1 \leq j \leq W)$
• マス $(0,0),(H,W)$ に魔物使いはおらず、マス $(0,0),(H,W)$ のある方角を向いている魔物使いもいない。
• マス $(0,0)$ から $(H,W)$ までの経路が存在する。

入力

入力はすべて整数である。

H W N
S_{1,1} S_{1,2} .. S_{1,W}
S_{2,1} S_{2,2} .. S_{2,W}
...
S_{H,1} S_{H,2} .. S_{H,W}

出力

moguさんが上下左右のマスへの移動を繰り返すことで町へ向かう際の、戦闘回数の最小値を1行に出力せよ。

サンプル

4 4 2
....
...<
.v..
....

1

例えば、次のように移動することで戦闘回数を $1$ 回にできます。戦闘回数を $0$ 回にすることはできないので、 $1$ を出力します。

***.
..*<
.v*.
..**

5 5 2
.....
...<.
.....
.>...
.....

0

次のように移動することで戦闘回数を $0$ 回にできます。

*****
...<*
*****
*>...
*****

5 5 4
.....
....<
....<
.....
..^^.

4

どのように移動しても戦闘回数は $4$ 回です。

5 5 2
.....
...v.
...^.
.....
.....

1

他の魔物使いの後ろに回ることによって魔物使いの視線をかいくぐることはできません。透視能力でもあるのでしょうか。