Problem 4 - Interpreter

Introduction

The problem involves creating an interpreter for a simple programming language called Slurm. The only statements in Slurm are output statements and assignment statements. There is only one type (integer) and variables are not declared. The only expressions are

variables;
integer constants;
function calls (there is only one function -- see below); and
two expressions of the previous three types joined by one of the operators * for multiplication, / for division, + for addition, and - for subtraction.

There are no loops, conditionals, or objects. There is only one function; this function reads an integer from standard input.

Input

The first line of input will be the number of lines in the following Slurm program and may be any nonnegative number. The next section of the input is the Slurm program. Output statements are given by listing the variable to output on a line. Assignment statements begin with the name of the variable to assign to followed by a single space and then the expression. Expressions are given by

the name of a variable, which may consist only of lower case letters;
an integer constant;
? to represent user input; or
an operator followed by two expressions of the first three types (with everything separated by single spaces).

For example, the C++ or Java code fragment

int a, b, c, result;

a = 2;
b = getUserInput();
c = b / 2;
result = c + getUserInput();
System.out.println(result); // or std::cout << result << std::endl;

would be written

a 2
b ?
c / b 2
result + c ?
result

in Slurm.

After the Slurm program is a line containing the number of times to run the program. This number may be any nonnegative integer. After that line is the user input to the program. You may assume that there is enough input to cover all of the requested runs and that each line contains an integer without any leading or trailing spaces.

The first call to ? should read input from the first line. The second call should read from the second line, and so forth. If two calls to ? are in the same statement, the left one is handled first.

Once one run finishes, all variables are reset to zero. The first input read by the next run should be the line immediately after the last line read by the previous run.

Output

The output must be the output produced by the Slurm program in the input. Any variables that are used before they are assigned to must be assumed to be zero. Your interpreter must terminate after the Slurm program is run the requested number of times, or if the program attempts to divide by zero, in which case the error message "DIVIDE BY ZERO" must be printed.

Example

Input:

6
a + 2 ?
square * a a
square
b ?
c / a b
c
3
7
3
4
0
1
1

Output:

81
3
36
DIVIDE BY ZERO