Turing's Program Halting Problem

Turing has given you a program. At the start of its execution, there is exactly one variable \(A\) with initial value \(0\). The program consists of \(n\) lines, numbered from \(1\) to \(n\). Each line is one of the following commands:

• A a: Set \(A \gets A + a\), then proceed to the next line.
• G x: Jump and execute line \(x\).
• I l r x y: If \(A \in [l,r]\) then jump to line \(x\); otherwise, jump to line \(y\).
• E: Immediately end the program.

It is guaranteed that the last line is E.

Turing wants you to determine whether the program, when executed starting from the first line, eventually terminates. Additionally, Turing requires you to output the final value of \(A\). In detail:

• If the program terminates, output the final value of \(A\>.
• If the program does not terminate and there is no moment after which \(A\) remains unchanged, output @Turing ?.
• If the program does not terminate but there exists a moment after which \(A\) is constant (i.e. every command executed after that moment does not change \(A\)), then output that constant value of \(A\).

Note: Although the program may appear to be a variation of the halting problem, the constraints allow you to simulate the program. You may assume that the input is small enough for simulation, but be careful of potential infinite loops. A repeated state \((\text{line}, A)\) indicates a cycle. If the cycle contains any A a command with \(a \neq 0\) (i.e. commands that modify \(A\) in a nonzero way), then there is no moment after which \(A\) becomes fixed.

inputFormat

The first line contains an integer \(n\) (the number of lines in the program). The following \(n\) lines each contain one command. Commands are given in one of the formats:

• A a
• G x
• I l r x y
• E

It is guaranteed that the last line is E.

outputFormat

If the program terminates, output the final value of \(A\). If the program does not terminate and there is no moment after which \(A\) remains unchanged, output @Turing ?. Otherwise, if the program does not terminate but eventually \(A\) becomes constant, output that constant value.

sample

4
A 5
I 0 5 4 3
A -1
E

5