题目描述

你知道吗？robot 这个单词诞生已经距今近 100 年了。这个单词在 1920 年 Karel Čapek 所作的科幻戏剧《罗萨姆的万能机器人》（R.U.R.）中首次出现。出于对这位捷克作家的敬意，很多年之后，在斯坦福大学诞生了一个名叫 Karel 的教育性编程语言。你的任务是写一个这个语言简化版本的解释器。

用 Karel 语言可以控制一个叫做 Karel 的机器人，这个机器人处在一个网格之中。网格中的一些格子是可以自由进出的，而一些格子内有障碍。Karel 永远会处在一个可以自由进出的格子，并且面向东南西北四个方向之一。两条基本命令是「向前移动」和「向左转」，这个编程语言也有简单条件判断语句和循环语句。这个语言最主要的教育意义在于有着定义新子程序来完成更复杂操作的可能性。

这个语言的简化版可以由如下语法描述：

<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>

有如下五种命令：

• m（向前移动）：向 Karel 面向的方向前进一格，除非那一格有障碍物。如果目标格有障碍物，这条命令无效；
• l（向左转）：使 Karel 向左转 $90$ 度；
• X：X 可以是任意大写字母，表示调用一个叫做 X 的子程序；
• i（if）：紧接着是一个单字母的条件，和在括号中的两个程序。如果条件满足，那么执行第一个程序，否则执行第二个程序；
• u（until）：紧接着是一个单字母的条件，和在括号里的一个程序。如果条件满足，则什么都不做，否则程序执行，这条命令会被重复。

条件或者是 b，或者是四个表示方向的字母 n，s，e，w 之一。b 仅表示 Karel 目前面向方向的下一格有障碍物。n，s，e，w 分别仅表示 Karel 面向北，南，东，西。

例如，一个简单的程序 ub(m) 的意思是：一直向前移动，直到遇到障碍物时停止。un(l) 的意思是：转向北面。一个子程序 R=lll 定义了一个新的子程序 R，这个子程序的意思是：转向右面。

输入格式

输入的第一行包含四个整数 $r,c,d,e$，$r,c$ 是 Karel 处在网格的大小，$d$ 是定义的子程序个数，$e$ 是需要执行的程序个数。

接下来 $r$ 行描述这个网格（从北到南进行），每行包含 $c$ 个字符（从西到东进行），每个字符是 . 和 # 之一。. 表示该格可自由进出，# 表示该格有障碍物。所有给定区域之外的方格都认为有障碍物，这意味着 Karel 不能离开这个区域。

接下来 $d$ 行，每行包含一个子程序的定义，开始是一个大写字母，表示子程序名称，紧接着是子程序体。没有任何两个子程序名称相同。子程序体中可能会调用尚未定义的子程序。

最后 $2e$ 行表述需要执行的程序。每个程序有两行。第一行包含两个正整数 $i,j$ 和一个字符 $h$，表示初始时 Karel 在第 $i$ 行第 $j$ 列的格子中，$h\in \{\texttt{n},\texttt{s},\texttt{e},\texttt{w}\}$ 表示初始时 Karel 面向的方向。保证初始位置是一个可自由进出的格子。第二行包含从这个位置出发，需要执行的程序。

所有子程序体和所有要执行的程序长度均在 $1$ 到 $100$ 之间（包括 $1$ 和 $100$），并且保证语法正确。给出的所有子程序体和要执行的程序只会调用定义过的子程序，并且行内没有空格。

输出格式

对于每个执行过的程序，输出程序结束后 Karel 的坐标和面向的方向。先输出两个正整数表示 Karel 的坐标，再输出一个字符表示方向，这个格式如同描述 Karel 的初始状态，详见输入格式。如果这个程序永远不会结束，输出 inf。

样例

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 w
inf
1 1 w
2 4 s
4 4 e
1 4 e
inf

数据范围与提示

对于全部数据，$1\le r,c\le 40,0\le d\le 26,1\le e\le 10,1\le i\le r,1\le j\le c$。