Rings and Runes

Frodo has entered the mines of Moria and reached a series of gates. Each gate bears an ancient riddle describing the state of a set of special control rings. From the riddle Frodo must decide whether the gate can be opened or whether it is simply a death trap.

A riddle is made of several runes. A valid rune contains exactly 3 statements about 3 different rings. Each statement is true or false depending on whether a specific ring is spinning or still. A riddle need not mention every ring in the gate's controlling set.

To open a gate the hobbits choose which rings to spin and which to leave still, then speak an incantation. The gate opens only if the whole riddle is satisfied, meaning every rune has at least one true statement.

Notation: a statement is written as a signed ring number. A positive number $r$ is true when ring $r$ is spinning; a negative number $-r$ is true when ring $r$ is not spinning. For example, the rune 1 -2 3 0 is true when (ring 1 is spinning) OR (ring 2 is not spinning) OR (ring 3 is spinning). The trailing 0 marks the end of the rune. A ring may appear at most once within a single rune, but the same ring may be reused across different runes.

• The first line contains an integer $g$ ($1 \le g \le 30$): the number of gates.
• For each gate, the first line contains two integers rings ($3 \le \text{rings} \le 22$) and runes ($1 \le \text{runes} \le 100$), separated by a space. Rings are numbered $1$ through rings; a riddle need not use every ring.
• The next runes lines each describe one rune as four space-separated integers $r_1\ r_2\ r_3\ 0$. The three statements are $r_1, r_2, r_3$ (each a signed 32-bit integer); the trailing $0$ terminates the rune.

For each gate, output exactly one line. If any rune contains an error, report only the single highest-priority error, using this priority order:

1. If any rune contains a null ring (a statement equal to $0$ or $-0$), the whole riddle is invalid. Output INVALID: NULL RING.
2. Otherwise, if any rune contains a statement $r$ with $r < -\text{rings}$ or $r > \text{rings}$, output INVALID: RING MISSING. (Do not report this if the riddle already has a null ring.)
3. Otherwise, if any single rune refers to the same ring more than once (for example -2 2 3 0 or 3 1 1 0), output INVALID: RUNE CONTAINS A REPEATED RING.
4. Otherwise the riddle is well-formed. Identical repeated runes count as one. If some choice of spinning and still rings satisfies every rune, output RUNES SATISFIED!. If no choice can satisfy every rune, output RUNES UNSATISFIABLE! TRY ANOTHER GATE!.