Hang or Not to Hang

Time limit1sMemory limit512 MB

Summary

Given a tiny assembly program with 32 boolean registers, arbitrary initial state, and nondeterministic RANDOM instructions, find the minimum number of cycles over all possible executions until STOP, or report HANGS.

Level: Medium6 of 10
Topics: BFS, Bit manipulation, Simulation, Graph
Solved: No attempts yet

Problem

Little Tom is learning to program. He has just written a few programs but is afraid to run them, because he does not know whether they will ever stop. Help him.

This is harder than it looks, because Tom's programs may behave nondeterministically.

Given one of Tom's programs, decide whether it can stop, and if so, find the shortest possible time before it stops.

Tom's computer has 32 one-bit registers, numbered from 0 to 31, and a program of n instructions, numbered from 0 to n − 1.

Below, MEM[a] denotes the contents of register a, with 0 ≤ a, b < 32, 0 ≤ x < n, and 0 ≤ c ≤ 1.

The instruction set is as follows:

Instruction	Semantics
`AND a b`	`MEM[a] := MEM[a] and MEM[b]`
`OR a b`	`MEM[a] := MEM[a] or MEM[b]`
`XOR a b`	`MEM[a] := MEM[a] xor MEM[b]`
`NOT a`	`MEM[a] := not MEM[a]`
`MOV a b`	`MEM[a] := MEM[b]`
`SET a c`	`MEM[a] := c`
`RANDOM a`	`MEM[a] :=` random value (0 or 1)
`JMP x`	jump to instruction `x`
`JZ x a`	jump to instruction `x` if `MEM[a] = 0`
`STOP`	stop the program

The last instruction of every program is always STOP (a program may contain more than one STOP). Every program starts at instruction 0. Before execution begins, the registers may hold arbitrary values. Each instruction (including STOP) takes one processor cycle.

Because of RANDOM instructions and the arbitrary initial register values, one program can run in many different ways. Among all runs that stop, report the smallest number of cycles. If no run ever stops, the program hangs.

Write a program that:

reads Tom's program,
computes the shortest possible running time,
prints the result.

Input

The first line contains an integer n (1 ≤ n ≤ 16), the number of instructions in the program. Each of the next n lines contains one instruction in the format given above. The only whitespace characters in the program are single spaces between successive tokens of an instruction.

Output

Print a single line with the shortest possible running time, measured in processor cycles. If the program can never stop, print the word HANGS instead.

Examples2

Example 1
Input
```
5
SET 0 1
JZ 4 0
RANDOM 0
JMP 1
STOP
```
Expected output
```
6
```

Example 2

Input

5
MOV 3 5
NOT 3
AND 3 5
JZ 0 3
STOP

Expected output

HANGS