The Halting Problem

The halting problem is the classic decision problem of telling whether a given program eventually finishes on a given input or runs forever. Alan Turing proved in 1936 that no method decides this for every program and input pair. This problem narrows the scope. Given a program written in the simple language defined below and the input to pass to it, decide whether the program halts, and if it does, report the value it returns.

The language works only with integers from 0 to 999 inclusive. The successor of 999 is 0 and the predecessor of 0 is 999. There are ten variables, R0 to R9. R0 receives the value the program was called with, that is the input parameter, and R9 always holds the output value, that is the return value. When execution starts, R0 holds the input parameter and every other variable is 0.

The basic operations are assignment MOV, addition ADD, subtraction SUB, multiplication MUL, integer division DIV, and remainder of integer division MOD. All of them have the syntax COMMAND OPERAND1,OPERAND2 with no space between the comma and the operands. OPERAND1 is one of the ten variables, and OPERAND2 is either a variable or an integer from 0 to 999. Every basic operation changes the value of OPERAND1, so MOV R4,100 assigns 100 to R4, and MUL R3,R8 multiplies R3 by R8 and stores the product in R3. The result of an addition, a subtraction, or a multiplication is reduced modulo 1000. DIV and MOD store 0 when OPERAND2 is 0, so DIV R4,0 is the same as MOV R4,0. Integer division keeps only the integer part of the quotient: the integer division of 7 by 2 is 3, with remainder 1.

There are six decision commands. IFEQ tests equality, IFNEQ inequality, IFG greater, IFL less, IFGE greater or equal, and IFLE less or equal. All of them have the syntax COMMAND OPERAND1,OPERAND2, where each operand is a variable or an integer from 0 to 999. So IFEQ R4,123 tests whether R4 equals 123. If the tested condition is true, the program keeps running from the next line. If it is false, the program jumps to the line right after the ENDIF that matches this decision command. Decision blocks nest, so count nested blocks when you look for the matching ENDIF. Every decision command has exactly one matching ENDIF.

Finally there are CALL and RET, both with the syntax COMMAND OPERAND, where the operand is a variable or an integer from 0 to 999. CALL calls the same program again, passing the value of the operand as the input parameter, so the fresh program starts with that value in R0. RET ends execution and returns the value of the operand as the output value. The last line of a program is always a RET. When a program calls itself with CALL and execution comes back, R9 holds the value the called program returned. All variables R0 to R9 are local, so a newly called program cannot change the values stored in the variables of the caller. The only exception is R9, which receives the return value.

The program below computes the factorial of a number.

Line 1: tests whether R0 is 0. If it is, the next line runs; if it is not, execution jumps to line 4, the line right after the matching ENDIF.

Line 2: returns 1 as the output value of the program.

Line 3: marks the end of the decision block opened on line 1.

Line 4: assigns the value of R0 to R1. R1 ← R0.

Line 5: subtracts 1 from R1. R1 ← R1 - 1.

Line 6: calls the program with R1 as the input parameter.

Line 7: stores in R2 the value of R9 returned by that call. R2 ← R9.

Line 8: multiplies R2 by R0. R2 ← R2 * R0.

Line 9: returns the value of R2 as the output value of the program.

Here is the summary of the commands.

The input holds several test cases. There are at most 50 test cases. Each test case begins with two integers $L$ and $N$, the number of lines of the program and the value of the input parameter passed to it ($1 \le L \le 100$, $0 \le N \le 999$). The next $L$ lines hold the program. You may assume it is always syntactically correct under the rules defined above. Every command and variable name uses uppercase letters only. The end of the input is marked by the case with $L = N = 0$, which must not be processed.

For each test case, print one line with the output value the program returns for the given input $N$, as an integer. If the program never halts, print a single asterisk *.