题目背景

Warning: If you submit a malicious program, you will be banned.

警告：恶意提交本题将被封号。

题目描述

Did you know that the word "robot" is almost 100 years old? It was first introduced in 1920, in the science-fiction theatrical play $R.U.R.$ , written by Karel Capek. As a tribute to this Czech writer, an educational programming language was named Karel many years later at Stanford University. Your task is to implement an interpreter of a simplified version of this programming language.

The Karel programming language controls a robot named Karel, who lives in a grid of unit squares. Some of the squares are free, while others contain a barrier. Karel always occupies one of the free squares and faces one of the four cardinal directions. The two basic commands are "move forward" and "turn left." The language also provides simple conditional and looping statements. The main educational potential of the language lies in the possibility of defining new procedures for more complex tasks.

Our simplified version of the language can be described 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 types of commands:

• $\texttt m$ ("move forward") advances Karel's position by one grid square in its current heading, unless there is a barrier, in which case the command has no effect.
• $\texttt l$ ("turn left") makes Karel turn left $90$ degrees.
• $\texttt X$ where $\texttt X$ is any uppercase letter, invokes the procedure named $\texttt X$.
• $\texttt i$ ("if") followed by a single-letter condition, and two programs in parentheses. If the condition is satisfied, the first program is executed. Otherwise, the second program is executed.
• $\texttt u$ ("until") followed by a single-letter condition, and a program in parentheses. If the condition is satisfied, nothing is done. Otherwise, the program is executed and then the command is repeated.

A condition can be either '$b$', which is satisfied if and only if there is a barrier in the next square in Karel's current heading, or one of the four directional letters n, s, e, or w, which is satisfied if and only if Karel's current heading is north, south, east, or west, respectively.

For instance, a simple program ub(m) can be understood to mean: “keep moving forward until there is a barrier," while un(l) means "turn to the north." A procedure definition R=lll defines a new procedure R which effectively means "turn right."

输入格式

The first line of input contains four integers $r, c, d$ and $e$, where $r$ and $c$ $(1 \leq r, c \leq 40)$ are the dimensions of the grid in which Karel lives, $d$ $(0 \leq d \leq 26)$ is the number of procedure definitions, and $e$ $(1 \leq e \leq 10)$ is the number of programs to be executed.

Then follow $r$ lines describing the grid (running north to south), each containing c characters (running west to east), each character being either . (denoting a free square) or # (denoting a barrier). All squares outside this given area are considered barriers, which means Karel may never leave the area.

Each of the next $d$ lines contains a procedure definition, associating a procedure name (one uppercase letter) with a program forming the procedure body. No procedure name is defined more than once. Procedure bodies may contain invocations of procedures that have not yet been defined.

The last $2e$ lines describe the programs to be executed. Each such description consists of a pair of lines. The first line of each pair contains two integers $i$ and $j$ and a character $h$, where $i$ $(1 \leq i\leq r)$ is the row and $j$ $(1 \leq j \leq c)$ is the column of Karel's initial position, and $h \in \{ \texttt n, \texttt s, \texttt e, \texttt w\}$ represents Karel's initial heading. It is guaranteed that the initial position is a free square. The second line of each pair contains a program to be executed from that initial position.

All procedure bodies and all programs to be executed are at least $1$ and at most $100$ characters long, syntactically correct, and only contain invocations of procedures that are defined. The lines with procedure definitions and programs to be executed contain no whitespace characters.

输出格式

For each program execution, output the final position of Karel after the complete program is executed from the respective initial position. Follow the format used to describe initial positions, that is, two numbers and a directional character. If a particular execution never terminates, output inf instead.

题目大意

题目描述

你知道“机器人”这个词已经有100年的历史了吗？它最早出现在1920年的科幻戏剧《R.U.R.R.U.R.》中，卡雷尔·卡佩克写的。为了向这位捷克作家致敬，一种教育编程语言在多年后在斯坦福大学被命名为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（“左转”）使卡雷尔左转9090度。

x，其中x是任何大写字母，调用名为x的过程。

i（“if”）后跟一个单字母条件，括号中有两个程序。如果满足条件，则执行第一个程序。否则，执行第二个程序。

u（“直到”），后跟一个单字母条件，括号中是一个程序。如果条件满足，则什么也不做。否则，将执行该程序，然后重复该命令。

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

例如，一个简单的程序ub（m）可以理解为“继续前进，直到有障碍物为止”，而un（l）表示“转向北方”。程序定义R=lll定义了一个新的程序R，它实际上意味着“右转”

输入的第一行包含四个整数r、c、dr、c、d和e，其中r和c（1≤r、 c≤40）是Karel居住的网格的尺寸，d（0≤D≤26）是程序定义的数量，e（1）≤E≤10） 是要执行的程序数。

然后沿着描述网格的r行（从北到南），每个包含c字符（从西到东），每个字符都是。（表示自由正方形）或#（表示障碍物）。该区域以外的所有广场都被视为障碍物，这意味着卡雷尔可能永远不会离开该区域。

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

最后两行描述了要执行的程序。每个这样的描述由一对行组成。每对的第一行包含两个整数ii和jj以及一个字符hh，其中i（1≤我≤r） 是行和j（1）≤J≤c） 是Karel初始位置的列，h∈{n，s，e，w}代表Karel的初始标题。保证初始位置为自由正方形。每对的第二行包含从该初始位置执行的程序。

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

输出格式

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

提示

Source: ICPC World Finals 2019.