Problem Statement

問題文を訂正しました（11:18）

問題文とサンプル入出力について，壊れていた一部の記号の表記を訂正しました（11:58）

盤面上にロボットと壁，ゴールが設置されており， ロボットの行動パターンを記述したプログラムが与えられる．

与えられるプログラムは以下のEBNFで表される．

プログラム := {文};
文 := if文|while文|動作文;
if文 := "[", 条件, プログラム, "]";
while文 := "{", 条件, プログラム, "}";
動作文 := "^"|"v"|"<"|">";
条件 := ["~"], "N"|"E"|"S"|"W"|"C"|"T";

「プログラム」は複数の「文」から0個以上の「文」からなり，1つ以上の文が存在する場合は1つ目の文から順番に1つずつ文が実行される．「文」は「動作文」，「if文」，「while文」のいずれかである．「動作文」は"^", "v","<",">"のいずれかであり，それぞれ以下の動作が実行される．

• "^": 前進
• "v": 後退
• "<": 左に90度回転
• ">": 右に90度回転

「if文」は"["，「条件」，「プログラム」，"]"を順番に並べたもので，以下の手順で実行される．

1. 「条件」の内容が真かどうか判定する
2. 判定が真なら「プログラム」の内容を実行し，このif文の処理を終了する
3. 判定が偽ならこのif文の処理を終了する

「while文」は"{"，「条件」，「プログラム」，"}"を順番に並べたもので，以下の手順で実行される．

1. 「条件」の内容が真かどうか判定する
2. 判定が真なら「プログラム」の内容を実行し，1に戻る
3. 判定が偽なら，このwhile文の処理を終了する

「条件」は"N", "E", "S", "W", "C", "T"のいずれかであり，先頭には"~"をつけることができる．それぞれの記述は以下の真偽値を表す．

• 先頭に"~"が付いている場合は真偽値が逆転
• "N": 北を向いているならば真，そうでなければ偽
• "E": 東を向いているならば真，そうでなければ偽
• "S": 南を向いているならば真，そうでなければ偽
• "W": 西を向いているならば真，そうでなければ偽
• "C": 目の前に壁があるならば真，そうでなければ偽
• "T": 常に真

ロボットは最初，北を向いているものとする．ロボットは壁を通ることができず，何もないマスのみを移動できる．もし，プログラムが壁の上を通るような動作を実行しようとした場合，ロボットは移動せずその場にとどまる．最後に，ロボットはゴールに到達した時，実行途中のプログラムが残っていたとしてもすべて中断して動作を停止する．

このとき，ロボットがゴールにたどり着くまでにどのぐらい時間がかかるのか知りたい．ロボットは条件判定やプログラムの読み込みに関しては非常に高速に実行できるので実際の動作時間を決定するのは「動作文」のみである． そこで，このロボットがゴールに辿り着くまでに「動作文」を何回実行するかを教えてほしい．

なお，壁の上を通るような動作を実行しようとして，実際には「動作文」の動作が行われなかった場合にも「動作文」は実行されたものとみなす．

Input

入力は以下の形式で与えられる．

$H$ $W$
$a_{1,1}a_{1,2} \ldots a_{1, W}$
$a_{2,1}a_{2,2} \ldots a_{2, W}$
:
:
$a_{H,1}a_{2,2} \ldots a_{H, W}$
$s$

$H$ は盤面の高さ，$W$ は盤面の幅を表す．

次に盤面を真上から見た状態が与えられる．この盤面は上，下，左，右がそれぞれ北，南，西，東に対応する． 各マスの状態を表す $a_{i,j}$ は以下のいずれかの文字である．

• "s": ロボット（ロボットの初期位置．このマスには壁がないことが保証されている）
• "g": ゴール
• "#": 壁（ロボットは壁の上を移動することはできない）
• ".": 何もないマス

$s$ にはロボットに与えられるプログラムが文字列として入力される．

Constraints

• $1 \leq H, W \leq 50$
• $1 \leq s$ の文字数 $\leq 1{,}000$
• $a_{i, j}$ は".", "#", "s", "g" のいずれか
• "s", "g"はそれぞれ1回しか登場しない
• $i = 1$ または $i = H$ または $j = 1$ または $j = W$ ならば $a_{i,j}$="#"（盤面の外周は壁で囲まれていることが保証されている）
• $s$ として与えられるプログラムは構文的に正しい

Output

たどり着ける場合は "到達するまでに実行した「動作文」の数" を，たどりつけない場合は "-1" を出力せよ．なお，壁の上を通るような動作を実行しようとして，実際には「動作文」の動作が行われなかった場合にも「動作文」が実行されたものとみなす点に注意せよ（入力例1）．

Sample Input 1

5 3
###
#g#
#.#
#s#
###
^<^<vv

Output for the Sample Input 1

5

Sample Input 2

5 7
#######
#.#g..#
#.###.#
#s....#
#######
{T{~C^}<}

Output for the Sample Input 2

17

Sample Input 3

5 7
#######
#.#g..#
#.###.#
#s....#
#######
{T{~C^}>}

Output for the Sample Input 3

-1