The keys of dark programming are described in page 1313 of the Necronomicon.
| C - The Necronomicon of Computing |
Necronomicon is the magic book discovered by famous writer H.P. Lovecraft, whose reading could lead to madness and even death. Nowadays, a new chapter which could not be decrypted by Lovecraft has been revealed: Dark Programming.
Dark programming can produce insanity in computer scientists who practice it. Arithmetical instructions are randomly changed with other instructions, conditional jumps are unpredictable because they depend on the will of the evil dead, and even dynamic memory is alive and it does not need to be released.
The keys of dark
programming are described in page 1313 of the Necronomicon.
Given a dark program, your task is to determinate whether or not it will end.
A
- arithmetical and assignment instructions; J
-
jumps; and C
- conditional jumps. Instructions are numbered sequentially, starting
from 1. The program begins at instruction 1 and ends when it reaches
past the
last instruction.
Jumps have the form:
J N
where N is the number of the instruction which is the destination of the jump. Conditional jumps have the form:
C N
The program can either jump to instruction N or continue to the following instruction. We cannot predict them. For example, if we have the dark program:
A
A
J 1
This program never finishes. The following is an example of a dark program that always finishes:
A
J 4
J 5
C 3
A
And this is a sample of a program that sometimes could finish or not:
A
A
C 2
A
Given a dark program, you have to determine if it always finishes, or it never finishes, or other case.
The first line contains a natural number, T, which indicates the number of test cases.
For each test case, the first line contains an integer, L, indicating the number of instructions of the dark program. L will not be greater than 1000. Then, there are L lines, one for each instruction. Each line can contain:
A
: for assignment instructionsJ
N
: for jump instructions, where N
is a natural number between 1 and L.C
N
: for conditional jumps, where N
is a natural number between 1 and L.For each test case, the output must be:
ALWAYS : if the program always
finishes.NEVER : if the program never
finishes.SOMETIMES : if the program can
finish sometimes depending on the execution.3
3
A
A
J 1
5
A
J 4
J 5
C 3
A
4
A
A
C 2
A
NEVER
ALWAYS
SOMETIMES