3113：The Halting Problem

The Halting Problem is a classic decision problem in computer science which basically requires to determine whether a given program will always stop (or terminate its execution) for an arbitrary given input or will execute infinitely. Alan Turing proved, in 1936, that it is impossible to solve the halting problem generalizing for any program-input pair. In this problem, however, given the description of a simple language, a program written in the language and an input for this program, you must determine whether the given program stops with the given input and, in the positive case, what output will be produced.

This language only works with integers from 0 to 999 (inclusive). In addition, the successor of 999 is 0, and the predecessor of 0 is 999. Moreover, it has ten variables (R0 to R9), among which R0 is always assigned the calling value of the program (that is, the input parameter) and R9 is always assigned the exit (return) value. At the beginning of execution of the program, the value 0 is assigned to all these variables, with the exception of R0, which receives the input parameter.

The basic operations are assignment (MOV), addition (ADD), subtraction (SUB), multiplication (MUL), integer division (DIV) and remainder of integer division (MOD). All these operations have the syntax COMMAND OPERAND1,OPERAND2 (without spaces between the comma and the operands), where COMMAND is one of these operations, OPERAND1 is one of the 10 variables (R0 to R9) and OPERAND2 can be one of the 10 variables or an integer value (between 0 and 999). All the operations modify the value of OPERAND1, consequently MOV R4,100 is equivalent to assigning the value 100 to R4, while MUL R3,R8 is equivalent to multiplying R3 by R8 and assigning the result to R3. The operation DIV, as well as MOD, returns 0 (zero) if OPERAND2 is 0 or the equivalent variable has the value 0. That is, DIV R4,0 is equivalent to multiplying MOV R4,0. By integer division, we mean the integral part of the quotient of the division (without the fractional part). For example, the integer division of 7 by 2 is 3 (with remainder 1).

There exist six decision flow commands: IFEQ (if equal), IFNEQ (if different), IFG (if greater), IFL (if less), IFGE (if greater or equal) and IFLE (if less or greater). The syntax of all of them is COMMAND OPERAND1,OPERAND2 (without spaces between the comma and the operands), where both OPERAND1 and OPERAND2 can be variables (R0 to R9) or integer values (between 0 and 999). Thus, the command IFEQ R4,123 is equivalent to testing whether R4 is equal to 123. When the tested condition is true, the program continues to execute normally the line subsequent to the decision command. When the condition is false, the program proceeds to execute the line subsequent to the nearest following ENDIF. All the decision commands must have a corresponding ENDIF command.

Finally, there exist the commands CALL and RET, both with the syntax COMMAND OPERAND, where OPERAND is a variable (R0 to R9) or a direct value (between 0 and 999). The command CALL calls the program recursively, passing OPERAND as the input parameter, that is, assigning the value of OPERAND to variable R0. And RET terminates the execution of the program, returning the value of OPERAND as the output result. The last line of the program will always be a command RET. It can be observed that, if the program calls itself through the command CALL, when execution returns, the value of R9 is going to be changed with the value returned by the program. Note also that all the variables (R0 to R9) are local, that is, a subsequent call to the program cannot change values saved in the variables of previous instance, with the exception of, naturally, the value of R9, which receives the return value of the called instance.

The following example illustrates a program that calculates the factorial of a number.

• The 1st line: Check if the value of R0 is 0, if true, execute the next line; if not, jump to the 4th line (past the nearest following ENDIF).
• The 2nd line: Return 1 as the output of the program.
• The 3rd line: Mark the end of the decision block started at the first line.
• The 4th line: Assign the value of R0 to R1 (R0 ← R1).
• The 5th line: Subtract 1 from R1 (R0 ← R0 - 1).
• The 6th line: Call the program passing R1 as the input parameter.
• The 7th line: Save the value of R9 (returned by the call before) in R2 (R2 ← R9).
• The 8th line: Multiply the value of R2 by R0 (R2 ← R2 * R0).
• The 9th line: Return the value of R2 as the output of the program.

The following table holds a resume of the commands for reference.

The input contains several test cases. Each test case starts with two integers, L and N, representing respectively the number of lines of the program (1 ≤ L ≤ 100) and the value of the input parameter of the program (0 ≤ N < 1000). The following L lines contain the program. It can be assumed that it is always syntactically correct in accordance with the rules defined above. All the commands (as well as the variables) only contain capital letters. The end of the input is marked by a case where L = N = 0 which should not be processed.