Description

你知道“机器人”这个词已经快 100 年了吗？它首次出现在 1920 年，由 Karel Capek 编写的科幻戏剧 $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>

有五种类型的命令：

• $\texttt m$（“前进”）使 Karel 在其当前方向上前进一个网格单元，除非前方有障碍物，在这种情况下命令无效。
• $\texttt l$（“左转”）使 Karel 左转 $90$ 度。
• $\texttt X$，其中 $\texttt X$ 是任何大写字母，调用名为 $\texttt X$ 的过程。
• $\texttt i$（“如果”）后跟一个单字母条件和两个括号中的程序。如果条件满足，则执行第一个程序。否则，执行第二个程序。
• $\texttt u$（“直到”）后跟一个单字母条件和一个括号中的程序。如果条件满足，则不执行任何操作。否则，执行程序，然后重复该命令。

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

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

Input Format

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

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

接下来的 $d$ 行中的每一行包含一个过程定义，将一个过程名称（一个大写字母）与形成过程主体的程序关联。没有过程名称被定义多于一次。过程主体可以包含尚未定义的过程调用。

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

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

Output Format

对于每个程序执行，输出从各自初始位置执行完整程序后 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

Hint

来源：ICPC 世界总决赛 2019。

题面翻译由 ChatGPT-4o 提供。