Karel's Simplified Interpreter

Robot Karel lives in a grid, where some squares are free and others have barriers. Karel is initially placed in a free square facing one of the cardinal directions. The robot can execute a sequence of commands written in a simplified programming language inspired by the famous play R.U.R. (which introduced the word "robot").

The commands are defined by the following grammar:

<program>   := "" | <command> <program>
<command>   := "m" | "l" | <proc-call> |
                 "i" <condition> "(" <program> ")(" <program> ")" |
                 "u" <condition> "(" <program> ")"
<condition> := "b" | "n" | "s" | "e" | "w"
<proc-call> := <uppercase-letter>
<proc-def>  := <uppercase-letter> "=" <program>

There are five command types:

• m (move forward): Advances Karel one square in its current heading if the square is free. If the square contains a barrier (or is outside the grid), the command does nothing.
• l (turn left): Rotates Karel 90° to the left.
• X (procedure call): Where X is any uppercase letter. This invokes the procedure defined for X.
• i (if): Followed by a condition letter and two programs in parentheses. If the condition is satisfied, the first program is executed; otherwise, the second program is executed.
• u (until): Followed by a condition letter and a program in parentheses. If the condition is already satisfied, nothing happens; otherwise, the program is executed and the command is repeated until the condition becomes true.

The condition letter can be:

• b: True if there's a barrier in the square immediately in front of Karel.
• n, s, e, w: True if Karel is currently facing north, south, east, or west, respectively.

For example, the program ub(m) instructs Karel to "keep moving forward until there is a barrier," and the procedure definition R=lll defines R to perform a right turn (since three left turns make a right turn).

Your task is to implement an interpreter for this simplified language.

inputFormat

The input is given in the following format:

R C
<grid row 1>
...
<grid row R>
r c d
P
proc_def_1
...
proc_def_P
program

where:

• R and C are the number of rows and columns of the grid.
• Each of the next R lines contains exactly C characters. A '.' denotes a free square and a '#' denotes a barrier.
• r and c (1-indexed) specify the starting row and column of Karel, and d is a letter (n, e, s, w) indicating the initial direction.
• P is the number of procedure definitions.
• Each procedure definition is given as an uppercase letter, followed by an '=', and then its program (e.g. R=lll).
• The last line contains the main program to be executed.

You may assume that the grid boundaries act as barriers.

outputFormat

Output the final position and direction of Karel in the format:

final_row final_column final_direction

Note: The row and column numbers are 1-indexed, and final_direction is one of n, e, s, or w.

sample

3 3
...
.#.
...
1 1 e
0
m

1 2 e