中島くんコントロール in 迷路（★★★★）

問題文

本問題は 中島くんコントロール の強化版です。

縦 $H$ マス、横 $W$ マスのグリッドがあります。上から $i$ 番目、左から $j$ 番目のマスをマス $(i, j)$ といいます。

S , G , . , # のいずれかである文字 $C_{i, j}$ はマス $(i, j)$ の状態を表します。それぞれ以下のように説明されます。

• S：スタート地点となるマス
• G：ゴール地点となるマス
• .：空きマス
• #：落とし穴のあるマス

はじめ、中島くんはスタート地点にいます。中島くんに対して、あなたが出力する文字列 $X$ の各文字で指示をすることができます。

中島くんは $i = 1, 2, \cdots, N$ の順に $X$ の $i$ 文字目で表される指示に従います。それぞれ以下のように説明されます。

• ^：上方向に $1$ マス移動する
• v：下方向に $1$ マス移動する
• <：左方向に $1$ マス移動する
• >：右方向に $1$ マス移動する

ただし、落とし穴のあるマスに移動した場合やグリッドの範囲外に移動した場合、不正解と判定されます。

ゴール地点に到達できる指示となる文字列 $X$ のうち、指示回数が最小となるものを $1$ つ提示してください。
ここで、そのような指示が必ず存在することが制約により保証されます。

ただし、答えが複数ある場合、そのいずれを出力しても正解と判定されます。

制約

• $1 \leqq H \leqq 100$
• $1 \leqq W \leqq 100$
• $C_{i, j}$ は S , G , . , # のいずれか
• $C_{i, j} =$ S となる $(i, j)$ はちょうど $1$ つ存在する
• $C_{i, j} =$ G となる $(i, j)$ はちょうど $1$ つ存在する
• 答えとなる $X$ は必ず存在する

入力

入力は以下の形式で標準入力から与えられます。

出力

中島くんに行う指示を表す文字列 $X$ を標準出力に出力してください。
答えが複数ある場合、そのいずれを出力しても正解と判定されます。

サンプル 1

4 5
S.#.G
.###.
.....
#..##

vv>>>>^^

下に $2$ 回、右に $4$ 回、上に $2$ 回移動するとゴール地点に到達できます。
これが最短経路です。

サンプル 2

4 4
S.##
....
#.#.
#..G

>vvv>>

以下の解答でも正解と判定されます。

v>>>vv

サンプル 3

8 47
...............................................
.....##.......####..##........###..............
....##.#.......##...##.........##.....######...
...##...#......##...######.....##...##......##.
..########.....##...##....##...##...########...
.G#.......#....##...##....##...##...##.......#.
##........###.####..######.....###....#S#####..
...............................................

v<<^<<^^^^^^<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<v<v<v<vv