你知道“机器人”（robot）这个词已经有近 100 年的历史了吗？它最早出现在 1920 年捷克作家卡雷尔·恰佩克（Karel Čapek）创作的科幻剧本《R.U.R.》中。为了向这位捷克作家致敬，多年后斯坦福大学将一种教育编程语言命名为 Karel。你的任务是实现该编程语言简化版本的解释器。

Karel 编程语言控制着一个名为 Karel 的机器人，它生活在一个由单位正方形组成的网格中。有些方格是空的，而另一些则包含障碍物。Karel 总是占据其中一个空方格，并面向四个基本方向之一。两个基本命令是“向前移动”（move forward）和“左转”（turn left）。该语言还提供了简单的条件语句和循环语句。该语言的主要教育潜力在于能够定义用于更复杂任务的新过程。

我们简化版本的语言可以通过以下语法描述：

:= "" |

:= "m" | "l" | | "i" "(" ")(" ")" | "u" "(" ")"

:= "b" | "n" | "s" | "e" | "w"

:=

:= "="

共有五种类型的命令：

• m（“向前移动”）将 Karel 的位置沿其当前朝向向前推进一个网格方格，除非前方有障碍物，在这种情况下该命令无效。
• l（“左转”）使 Karel 向左旋转 90 度。
• X（其中 X 为任意大写字母）调用名为 X 的过程。
• i（“如果”）后跟一个单字母条件和括号内的两个程序。如果条件满足，则执行第一个程序。否则，执行第二个程序。
• u（“直到”）后跟一个单字母条件和括号内的一个程序。如果条件满足，则什么都不做。否则，执行该程序，然后重复执行该命令。

条件可以是 ‘b’，当且仅当 Karel 当前朝向的下一个方格有障碍物时满足；或者是四个方向字母 ‘n’、‘s’、‘e’ 或 ‘w’ 之一，当且仅当 Karel 当前的朝向分别为北、南、东或西时满足。

例如，简单的程序 ub(m) 可以理解为：“持续向前移动直到遇到障碍物”，而 un(l) 意味着“转向北方”。过程定义 R=lll 定义了一个新过程 ‘R’，其效果是“向右转”。

输入格式

输入的第一行包含四个整数 $r, c, d$ 和 $e$，其中 $r$ 和 $c$ ($1 \le r, c \le 40$) 是 Karel 生活的网格尺寸，$d$ ($0 \le d \le 26$) 是过程定义的数量，$e$ ($1 \le e \le 10$) 是要执行的程序数量。

接下来是 $r$ 行描述网格（从北向南），每行包含 $c$ 个字符（从西向东），每个字符要么是 ‘.’（表示空方格），要么是 ‘#’（表示障碍物）。给定区域之外的所有方格都被视为障碍物，这意味着 Karel 永远不会离开该区域。

接下来的 $d$ 行，每行包含一个过程定义，将一个过程名称（一个大写字母）与构成过程体的程序关联起来。没有过程名称会被定义超过一次。过程体可能包含尚未定义的过程调用。

最后 $2e$ 行描述要执行的程序。每个描述由一对行组成。每对的第一行包含两个整数 $i$ 和 $j$ 以及一个字符 $h$，其中 $i$ ($1 \le i \le r$) 是行号，$j$ ($1 \le j \le c$) 是列号，表示 Karel 的初始位置，$h \in \{n, s, e, w\}$ 表示 Karel 的初始朝向。保证初始位置是一个空方格。每对的第二行包含要从该初始位置执行的程序。

所有过程体和所有要执行的程序长度至少为 1 且最多为 100 个字符，语法正确，并且仅包含已定义的过程调用。包含过程定义和要执行的程序的行不包含任何空白字符。

输出格式

对于每个程序执行，输出 Karel 在从各自初始位置执行完完整程序后的最终位置。遵循描述初始位置的格式，即两个数字和一个方向字符。如果某个特定的执行永远不会终止，则输出 inf。

样例

样例输入 1

4 8 5 7
.......#
..#....#
.###...#
.....###
R=lll
G=ub(B)
B=ub(m)lib(l)(m)
H=ib()(mmHllmll)
I=III
1 1 w
G
1 1 e
G
2 2 n
G
2 6 w
BR
4 1 s
ib(lib()(mmm))(mmmm)
1 1 e
H
2 2 s
I

样例输出 1

1 1 w
inf
1 1 w
2 4 s
4 4 e
1 4 e
inf