問題文

うしくんとうくくんが H \times W マスの迷路の中に閉じ込められてしまった。
とりあえず、いつのまにかポケットに入っていた地図を元に合流したい。

地図によると迷路は以下の6種類のマスからできているようだ。

# 壁       通ることはできない
. 床       隣接する上下左右方向に移動できる(必ずしも移動する必要はない)
> 動く床(右)   右方向のみに移動できる(必ず移動を試みる)
< 動く床(左)   左方向のみに移動できる(必ず移動を試みる)
^ 動く床(上)   上方向のみに移動できる(必ず移動を試みる)
v 動く床(下)   下方向のみに移動できる(必ず移動を試みる)

壁の存在する方向に移動しようとした場合、移動できず移動元のマスに留まる。

うしくんとうくくんの初期位置の候補が Q 個与えられるので、各初期位置について、二人が合流するまでにかかる最短の移動回数を求めよ。

一回の移動の際にはうしくんとうくくんは独立に行動できる。また、うしくんとうくくんは心が通じ合っているので、お互いに最適な行動を取ることが可能である。

制約

• 3 \leq H, W \leq 30
• 1 \leq Q \leq 10^5
• S_i (1 \leq i \leq H) は上記の 6 種類の文字のみからなる長さ W の文字列である。
• 2 \leq SX_i, GX_i \leq W - 1 (1 \leq i \leq Q)
• 2 \leq SY_i, GY_i \leq H - 1 (1 \leq i \leq Q)
• 与えられる入力において、迷路の外側 1 マスは壁で囲われていることが保証されている。
• 与えられる入力において、うしくんとうくくんの初期位置に壁があることはない。

入力例 1

5 4 3
####
#..#
#.##
##.#
####
2 2 2 2
2 3 3 2
2 2 3 4

出力例 1

0
1
-1

最初から同じマスにいることもあります。 動く床が一つもないこともあります。

入力例 2

5 5 2
#####
#<..#
###^#
#...#
#####
4 2 2 4
2 2 2 4

出力例 2

3
6

入力例 3

10 13 10
#############
#vvv>vvv#v<.#
#.^.^<#>.v<.#
#.#>v<<<>>v.#
#^v<.v^v>#<<#
#^.>vv^.^.^^#
#<><vv>^vv^>#
##<.>^>v.^<<#
#.v.^v.>><v^#
#############
10 4 8 6
11 7 11 5
8 9 7 8
12 4 5 6
5 6 8 6
12 3 11 7
2 5 8 9
10 4 6 8
4 3 4 3
7 7 3 6

出力例 3

-1
2
3
-1
10
3
-1
-1
0
9