human
A robot, a wall, and a goal are installed on the board, and a program that describes the behavior pattern of the robot is given.

The given program is represented by the following EBNF.

Program: = {statement};
Statement: = if statement | while statement | action statement;
if statement: = "[", condition, program, "]";
while statement: = "{", condition, program, "}";

Action statement: = "^" | "v" | "<" | ">";
Condition: = ["~"], "N" | "E" | "S" | "W" | "C" | "T";

A "program" consists of 0 or more "sentences", and if there is one or more sentences, the sentences are executed one by one in order from the first sentence. A "statement" is one of an "action statement", an "if statement", and a "while statement". The "action statement" is one of "^", "v", "<", ">", and the following actions are executed respectively.

* "^": Advance
* "v": Retreat
* "<": Rotate 90 degrees to the left
* ">": Rotate 90 degrees to the right


The "if statement" is an arrangement of "[", "condition", "program", "]" in order, and is executed by the following procedure.

1. Determine if the content of the "condition" is true
2. If the judgment is true, execute the contents of the "program" and end the processing of this if statement.
3. If the judgment is false, the processing of this if statement ends.


A "while statement" is an arrangement of "{", "condition", "program", and "}" in order, and is executed by the following procedure.

1. Determine if the content of the "condition" is true
2. If the judgment is true, execute the contents of "Program" and return to 1.
3. If the judgment is false, the processing of this while statement ends.


The "condition" is one of "N", "E", "S", "W", "C", "T", and can be prefixed with "~". Each description represents the following boolean values.

* If "~" is added at the beginning, the boolean value is reversed.
* N: True if facing north, false otherwise
* E: True if facing east, false otherwise
* S: True if facing south, false otherwise
* W: True if facing west, false otherwise
* C: True if...
def m Give me a Python program to determine if the content of the "condition" is true?
assistant
#Here is Python program to determine if the content of the "condition" is true
.
ain():
    H, W = map(int, input().split())
    MP = [input() for i in range(H)]
    for i in range(H):
        mi = MP[i]
        for j in range(W):
            c = mi[j]
            if c == 's':
                sx = j; sy = i
            elif c == 'g':
                gx = j; gy = i
    S = input()
    L = len(S)
    X = [-1]*len(S)
    st = []
    for i, c in enumerate(S):
        if c in "[{":
            st.append(i)
        elif c in "]}":
            k = st.pop()
            X[k] = i
            X[i] = k
    ds = "WNES"
    dd = ((-1, 0), (0, -1), (1, 0), (0, 1))
    U = set()
    ans = 0
    d = 1
    cur = 0
    def check(c, x, y, d):
        if c == "T":
            return 1
        if c in ds:
            return (d == ds.index(c))
        dx, dy = dd[d]
        return MP[y+dy][x+dx] == "#"
    x = sx; y = sy
    ok = 0
    while 1:
        if x == gx and y == gy:
            ok = 1
            break
        br = 0
        while cur < L:
            key = (x, y, d, cur)
            if key in U:
                br = 1
                break
            U.add(key)

            c = S[cur]
            if c in "[{":
                c = S[cur+1]
                if c == '~':
                    if not check(S[cur+2], x, y, d):
                        cur += 3
                    else:
                        cur = X[cur]+1
                else:
                    if check(c, x, y, d):
                        cur += 2
                    else:
                        cur = X[cur]+1
            elif c == "]":
                cur += 1
            elif c == "}":
                cur = X[cur]
            else:
                break
        if cur == L or br:
            break
        c = S[cur]
        dx, dy = dd[d]
        assert c in "<>^v"
        if c == "^":
            if MP[y+dy][x+dx] != '#':
                x += dx; y += dy
        elif c == "v":
            if MP[y-dy][x-dx] != '#':
                x -= dx; y -= dy
        elif c == "<":
            d = (d - 1) % 4
        else: # c == ">"
           ...