Problem 1007: The Matrix

(ACM S.E. U.S.A. Regional 2003, problem 7, corrected)

Description

Yes, with The Matrix Revolutions due in theaters next month, it's time to worry about the plot to The Matrix: 4. And what could be more exciting than computer programming? So, a scriptwriter has asked you to help create an interpreter for a new programming language, the Foo Language, or just FooL for short.

Each FooL program will run on a 2 dimensional fixed-size matrix of cells. There is a single pointer, which moves over the matrix. At the beginning of every program, the array is initialized to all zeroes, and the pointer points at the element at the upper left, called position [0, 0]. A matrix with 2 rows and 4 columns would initially look like:

where the shaded cell indicates the location of the pointer. A FooL program is a sequence of one or more FooL instructions. There are a number of different types of FooL instructions.

Movement instructions

The pointer can be moved using the following instructions:
     >  Move the pointer one cell to the right (do not change the row).
<Move the pointer one cell to the left (do not change the row).
^Move the pointer to the cell above (do not change the column).
vMove the pointer to the cell below (do not change the column).
Since there is no escaping the matrix, the pointer will wrap-around when it reaches the edge of the matrix. For example, in the matrix above, the instruction ^ will move the pointer to row 1, column 0 and the instruction < after that would move it to row 1, column 3.

Data instructions

FooL can access and change the data under the pointer:
     +Increment the content of the location at the pointer by 1.
-Decrement the content of the location at the pointer by 1.
=(r,c) Copy the value at location [r, c] to the location pointed to by the pointer. You may assume the location [r, c] is within the bounds of the matrix.

Input and output instructions

FooL can do input and output to the location at the pointer:
     IStore input to the location pointed by the pointer
OOutput the integer value of value in the location at the pointer
A 
 		Output the value in the location at the pointer interpreted as an ASCII character. If the value in the cell is less than 32 or greater than 126, print an underscore ('_').

Control structures

FooL has an if statement and while loop. The if statement has the structure:
    ? if-clause : else-clause X
If the location under the pointer is non-zero, the instructions between the '?' and ':' are executed, and then control passes to the instruction following the 'X'. If the location under the pointer is zero, the instructions between the ':' and the 'X' are executed. For example, if the location under the pointer has the value 3,
    ?O-:+OX
will output 3 and subtract one from the location. If the value under the pointer is 0, then that value would be incremented, and the program would output 1.
Either if-clause or else-clause (or both) may be empty.

The while statement has the structure:
    W statements X
While the location under the pointer is non-zero, the statements between the 'W' and 'X' are executed. The condition is checked before each iteration of the statements. For example, if the value under the pointer is 3,
    WO-X
will output successively 3, 2, 1, and the value 0 will be under the pointer.
The statements in a while statement may be empty.

An 'X' will match with the nearest unmatched '?', ':', or 'W' preceding the 'X'.

Syntax issues

Of course, there can be comments in a FooL program. Comments are included in pairs of exclamation marks. Everything from the first exclamation point to the second, inclusive, will be ignored by FooL. A FooL program may have any amount of embedded white space, so the FooL instruction ?O-:+OX could also be written: 

    ? ! if pointing at value not equal to 0 !
      O- ! Print the value and subtract 1 !
    : ! otherwise !
      +
      O ! Add first, then print !
    X   ! End the if statement !

Input Format

The input file for this program will contain one or more data sets. The first line of a data set contain four integer values R, C, P, I, separated by white space, with 0 < R,C <= 50, 0 < P <= 1000, and 0 <= I <= 1000. R and C indicate the number of rows and columns of the matrix. Integer P indicates the length of the program in lines, and I indicates the number of lines in the input data. After the first line of each data set, there will be P lines (each with fewer than 81 characters) containing the FooL program to be interpreted. The next I lines will each contain one input value, n, with 0 <= n <= 200.

The given FooL programs are guaranteed to reach termination, are syntactically correct, will not generate erroneous conditions. There will always be enough input to run the program and there might be more than is necessary for the program to reach its conclusion.

The end of the data sets is represented by the end of the input file.

Output Format

Each data set should produce a line looking like:

Program n:

Where n is a sequential number (starting at 1 for the first input data set). This will be followed by the FooL program output characters on a single line, without separators. You should include a blank line after each data set.

Sample Input

2 2 1 1
IWO-X
3
1 2 1 12
IW>IA<-X
11
72
101
108
108
111
32
87
111
114
108
100
2 2 13 1
! A program to compute the sum of 1 ..n !
I   ! Read n !
>=(0,0) ! Copy to counter !
W
-v< ! Decrement counter !
=(0,1)
   W ! Add counter to sum !
     ^+^
     -
   X
<v
X
<O ! Print results !
12

Sample Output

Program 1:
321

Program 2:
Hello World

Program 3:
78

End of Problem