问题描述

在棋盘上放置了机器人、墙壁和目标。给定描述机器人动作模式的程序。

给定的程序用以下EBNF表示:

程序 := {语句};
语句 := 如果语句|循环语句|动作语句;
如果语句 := "\[", 条件, 程序, "\]";
循环语句 := "{", 条件, 程序, "}";
动作语句 := "^"|"v"|"<"|">";
条件 := \["~"\], "N"|"E"|"S"|"W"|"C"|"T";

"程序"由0个或多个"语句"组成，当存在一个或多个语句时，语句将依次执行。"语句"可以是"动作语句"、"如果语句"或"循环语句"之一。"动作语句"可以是"^"，"v"，"<"或">"，分别对应以下动作：

• "^"：向前移动
• "v"：向后移动
• "<"：向左旋转90度
• ">"：向右旋转90度

"如果语句"由"["，"条件"，"程序"，"]"依次组成，按照以下步骤执行：

1. 判断条件的值是真还是假
2. 如果条件为真，则执行"程序"的内容，然后结束该如果语句的处理
3. 如果条件为假，则结束该如果语句的处理

"循环语句"由"{"，"条件"，"程序"，"}"依次组成，按照以下步骤执行：

1. 判断条件的值是真还是假
2. 如果条件为真，则执行"程序"的内容，然后返回步骤1
3. 如果条件为假，则结束该循环语句的处理

"条件"可以是"N"，"E"，"S"，"W"，"C"，"T"之一，可以在开头加上"~"来表示该条件的否定。每种条件表示以下真假值：

• 如果条件以"~"开头，则取反
• "N"：如果朝北则为真，否则为假
• "E"：如果朝东则为真，否则为假
• "S"：如果朝南则为真，否则为假
• "W"：如果朝西则为真，否则为假
• "C"：如果正前方有墙壁则为真，否则为假
• "T"：始终为真

机器人最初面向北方。机器人不能穿过墙壁，只能移动到空白方块上。如果程序要执行机器人通过墙壁的动作，机器人将不移动并保持原地。最后，当机器人到达目标时，无论执行中是否还有程序，机器人都会停止运动。

在这种情况下，我想知道机器人到达目标需要多长时间。机器人在条件判断和程序读取方面非常快，因此实际运行时间仅由"动作语句"确定。因此，我希望你告诉我机器人在到达目标之前执行了多少次"动作语句"。

请注意，即使尝试执行通过墙壁的动作实际上没有执行"动作语句"，它也被视为已执行。

输入

输入以以下格式给出。

$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$ 是以字符串形式输入的机器人程序。

约束条件

• $1 \leq H, W \leq 50$
• $1 \leq s$ 的字符数 $\leq 1{,}000$
• $a\_{i, j}$ 是".", "#", "s", "g"之一
• "s"和"g"分别只出现一次
• 如果 $i = 1$ 或 $i = H$ 或 $j = 1$ 或 $j = W$ 则 a\_{i,j}="#"（棋盘的外围围以墙壁包围）
• 作为给定的程序在语法上是正确的

输出

如果能够到达目标，则输出从开始到达目标时执行的"动作语句"的数量；如果无法到达目标，则输出"-1"。请注意，即使尝试执行通过墙壁的动作实际上没有执行"动作语句"，它也被视为已执行。（见示例1）

示例输入1

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

### 示例输出1

```plain
5```

### 示例输入2

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

### 示例输出2

```plain
17```

### 示例输入3

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

### 示例输出3

```plain
-1```