We are glad to present to you a new programming language URCAPL (Universal Reusable Cool and Amazing Programming Language).
if you know anything about the programming language Befunge and the syntax described below seems familiar to you, we still recommend you to read the description of the language URCAPL. It was invented especially for this contest and has little in common with Befunge.
URCAPL works only with integers not exceeding 105 by absolute value. Numbers are stored in 27 registers: one current register and 26 memory registers encoded by uppercase English letters from A to Z. Initially all the registers contain the number 0.
A program is a two-dimensional field of size H × W; each cell contains some operator. A program is executed by a pointer, which is located in some cell of the field and has one of the four possible motion directions: up, down, to the right and to the left. When the execution of a program starts, the pointer is in the upper left corner of the field, and the direction of its motion is to the right. During the execution, the motion direction may change depending on the operator written in the cell where the pointer is at the moment. The work of a program is divided into steps. At each step, the operator in the pointer cell is first executed, and then the pointer moves one cell in the current direction.
The list of operators:
- “^”, “>”, “v”, “<” — change the motion direction to up, right, down, or left, respectively;
- “.” — do nothing;
- “A”…“Z” — swap the integers in the current register and the register denoted by the letter;
- “?” — read the integer from the input and write it to the current register (the old value of the current register is deleted);
- “!” — write the integer in the current register to the output and set the value of the current register to 0;
- “+” — increase the number in the current register by one;
- “-” — decrease the number in the current register by one;
- “@” — (the conditional operator) if the number in the current register is 0, change the motion direction counterclockwise; otherwise, change it clockwise;
- “#” — terminate the execution of the program immediately.
If the number in the current register exceeds 105 by absolute value, the program terminates with OVERFLOW ERROR.
If the pointer moves out of the field, the program terminates with RUNTIME ERROR.
If the termination operator is not executed during 106 steps and none of the above two errors occurs, then the program terminates with TIME LIMIT EXCEEDED.
You are required to write an URCAPL interpreter. For a given URCAPL program and input data, the interpreter should produce the output of the program.
The first line contains integers H and W (1 ≤ H, W ≤ 100), which are dimensions of the field.
Then you are given a table with H rows and W columns, which is a syntactically correct URCAPL program (i.e., it contains only the operators described above).
The next line contains the number n of integers in the input of the program (1 ≤ n ≤ 105),
and the input of the program is given in the following n lines: each line contains one integer with absolute value not exceeding 105.
If the program has read n numbers during its execution, then all the subsequent read requests will return the last integer from this list.
If the program reads not all integers from the list during its execution, this is not an error.
For each output command in the URCAPL program, you should output a number in a separate line. If one of the errors OVERFLOW ERROR, RUNTIME ERROR, or TIME LIMIT EXCEEDED occurs, output the corresponding message in a separate line.
Note that the program terminates immediately after the first error. For example, if OVERFLOW ERROR and RUNTIME ERROR occur during the same step, you should output only the message “OVERFLOW ERROR” (without quotation marks), because the operator in the pointer cell is executed first and only after that the pointer moves.
TIME LIMIT EXCEEDED
Problem Author: Kirill Borozdin
Problem Source: Ural Regional School Programming Contest 2014