#D7029. Halting Problem
Halting Problem
Halting Problem
Have you ever had an infinite loop when you ran a hard-working program? It would be convenient to be able to determine in advance whether a program will stop executing without having to execute it.
Unfortunately, it is not possible to make such a decision for any program in the programming language you normally use. However, if you have a programming language that is much less computationally powerful, you may be able to write a program that determines if a program written in that language will stop.
Consider a programming language called TinyPower. Programs in this language are line sequences. On each line of the program, write the line number at the beginning and one sentence after it. The types of sentences that can be written in this language are as follows.
| Sentence type | Behavior |
|---|---|
| ADD var1 var2 var3 | Assign the result of adding the value of variable var2 and the value of var3 to variable var1 |
| ADD var1 var2 con | Assign the result of adding the value of the variable var2 and the constant con to the variable var1 |
| SUB var1 var2 var3 | Assign the result of subtracting the value of var3 from the value of variable var2 to variable var1 |
| SUB var1 var2 con | Substitute the result of subtracting the constant con from the value of the variable var2 into the variable var1 |
| SET var1 var2 | Assign the value of variable var2 to variable var1 |
| SET var1 con | Assign the constant con to the variable var1 |
| IF var1 dest | Jump to line number dest only if the value of variable var1 is non-zero |
| HALT | Stop the program |
Line numbers are positive integers, and the same line number will never appear more than once in the program. Variables are represented by a single lowercase letter, and constants and variable values are integers. No variable declaration is required, the initial value of the variable is 0.
Program execution starts with the first statement, and the statements are executed in the order in which they are lined up. However, as written in the table above, if the value of the variable in the IF statement is not 0, jump to the line specified by the line number written after the variable and start from the statement written in that line. Continue running. The program will stop when:
- When the HALT statement is executed.
- When trying to assign a negative integer or an integer greater than or equal to 16 to a variable (the value of the variable is not updated).
- When trying to jump to a line number that does not appear in the program.
- When you do not jump to any line from the last statement of the program.
Create a program that determines if a TinyPower program, given it, will stop.
Input
The input is given in the following format.
N stmt1 stmt2 :: stmtN
The number of lines N (1 ≤ N ≤ 50) of the program is given on the first line. The following N lines are given the statement stmti of the TinyPower program. stmti is given in one of the following formats:
line ADD var1 var2 var3
Or
line ADD var1 var2 con
Or
line SUB var1 var2 var3
Or
line SUB var1 var2 con
Or
line SET var1 var2
Or
line SET var1 con
Or
line IF var1 dest
Or
line HALT
line, dest (1 ≤ line, dest ≤ 1000) is the line number, varj (one lowercase letter) is the variable, and con (0 ≤ con ≤ 15) is the constant. The delimiter in stmti is one blank character. It is assumed that one or more variables always appear in the program, and only five different variable names appear.
Output
When the program stops, the results of the variables appearing in the program are output in the lexicographic order of the variable names, separated by line breaks, and when it does not stop, "inf" is output. The result of the variable is output by separating the variable name and the value of the variable with "=".
Examples
Input
6 10 SET c 1 20 SET i 5 100 ADD s s i 110 SUB i i c 120 IF i 100 200 HALT
Output
c=1 i=0 s=15
Input
3 10 SET c 1 120 IF c 10 20 HALT
Output
inf
Input
3 111 SET c 1 12 SUB c c 2 777 SET a 4
Output
a=0 c=1
inputFormat
Input
The input is given in the following format.
N stmt1 stmt2 :: stmtN
The number of lines N (1 ≤ N ≤ 50) of the program is given on the first line. The following N lines are given the statement stmti of the TinyPower program. stmti is given in one of the following formats:
line ADD var1 var2 var3
Or
line ADD var1 var2 con
Or
line SUB var1 var2 var3
Or
line SUB var1 var2 con
Or
line SET var1 var2
Or
line SET var1 con
Or
line IF var1 dest
Or
line HALT
line, dest (1 ≤ line, dest ≤ 1000) is the line number, varj (one lowercase letter) is the variable, and con (0 ≤ con ≤ 15) is the constant. The delimiter in stmti is one blank character. It is assumed that one or more variables always appear in the program, and only five different variable names appear.
outputFormat
Output
When the program stops, the results of the variables appearing in the program are output in the lexicographic order of the variable names, separated by line breaks, and when it does not stop, "inf" is output. The result of the variable is output by separating the variable name and the value of the variable with "=".
Examples
Input
6 10 SET c 1 20 SET i 5 100 ADD s s i 110 SUB i i c 120 IF i 100 200 HALT
Output
c=1 i=0 s=15
Input
3 10 SET c 1 120 IF c 10 20 HALT
Output
inf
Input
3 111 SET c 1 12 SUB c c 2 777 SET a 4
Output
a=0 c=1
样例
3
111 SET c 1
12 SUB c c 2
777 SET a 4a=0
c=1