\includegraphics{https://static.e-olymp.com/content/a3/a30bc66e41bbb49b6cd74a00111097d1e71da015.jpg} Frodo has entered the mines of Moria and encountered a series of gates. Each gate has written upon it an ancient riddle describing the state of a set of special rings which control that particular gate. By examining the riddle, Frodo can determine whether or not the gate can be opened, or if it is simply a death trap. Riddles consist of multiple runes. A valid rune contains exactly \textbf{3} statements about \textbf{3 }different rings. Each statement in a rune is either true or false, depending on the state (spinning or not spinning) of a speci c ring in the set of rings controlling the gate. The riddle for a particular gate does not have to use all of the possible rings contained in the gate's controlling set. To open the gates, the hobbits must read the riddle, then, decide which of the rings to spin, and which of the rings to leave alone. Once they have the correct rings spinning, they say an incantation, and if the entire riddle for the gate is satis ed the gate will open. For the gate to open, every rune in the riddle must have at least one statement in it that is true. For example, consider a speci c rune: \textbf{1 -2 3 0}. This rune will be true if (ring \textbf{1} is spinning) \textbf{OR} (ring \textbf{2} is \textbf{NOT} spinning) \textbf{OR} (ring \textbf{3} is spinning). (NOTE: The \textbf{0} indicates the end of a rune, and at least one of the statements in that rune must be true for that speci c rune to be true.) If a ring number in a rune is negative (e.g., \textbf{-2}), it means that ring \textbf{2} must \textbf{NOT} be spinning for that particular statement in the rune to be true. If the ring number is positive, (e.g., \textbf{3}) it means that ring \textbf{3} MUST be spinning for that statement in the rune to be true. A speci c ring may only appear one time in a speci c rune, however, a ring may be used multiple times in the entire riddle, just not in the same rune! \InputFile The input will consist of the following: \begin{itemize} \item The first line of input contains a single integer \textbf{g} (where \textbf{1} ≤ \textbf{g} ≤ \textbf{30}), which denotes the number of gates with riddles to be decoded. \item The first line for each gate contains two integers, \textbf{rings} (where \textbf{3} ≤ \textbf{rings} ≤ \textbf{22}) and \textbf{runes} (where \textbf{1} ≤ \textbf{runes} ≤\textbf{100}), separated by a space. \textbf{rings} is the number of rings in the controlling set; each ring is numbered from \textbf{1}to \textbf{rings}, and riddles are not required to use every possible ring. \textbf{runes} is the number of runes that must be satis ed by the set of rings. \item The next \textbf{runes} lines describe individual runes that specify the relationships between the rings for that gate. Each rune is represented by a single line containing four numbers: \textbf{r_1}, \textbf{r_2}, \textbf{r_3}, and \textbf{0}, where each of these numbers are separated by a space. The first three numbers are \textbf{32}-bit integers. \end{itemize} \OutputFile Each gate contains exactly one riddle (consisting of multiple runes), and your algorithm should output exactly one line for each gate. If one or more runes in a riddle contain errors, output only the highest priority error for that riddle. The priority of errors is described below: \begin{itemize} \item If ANY rune in a riddle contains a statement about a null ring, e.g., \textbf{0} or \textbf{-0}, this is the most severe error in a riddle, and the whole riddle is invalid. Output "\textbf{INVALID: NULL RING}" as the highest priority error. \item If ANY rune in a riddle contains a statement \textbf{r} or \textbf{-r}, where (\textbf{r} < \textbf{-rings}) or (\textbf{r} > \textbf{rings}) then this is the SECOND most severe error in a riddle, and so output "\textbf{INVALID: RING MISSING}". NOTE: Do NOT output this message if the riddle contained a NULL ring! \item If ANY individual rune refers to the same ring more than once (e.g. \textbf{-2 2 3 0} OR \textbf{3 1 1 0}), this is the THIRD most severe error, so output "\textbf{INVALID: RUNE CONTAINS A REPEATED RING}". Again, don't output this message if a higher priority error occurred somewhere in the riddle. \item Riddles may contain repeated runes. Treat all of these repeated runes as a single rune; since they are identical, if one is true all of the repeated runes will be true. \item If there is a con guration of spinning/still rings that satis es all the runes in the riddle, output "\textbf{RUNES SATISFIED!}" \item If there is no possible con guration of spinning/still rings that satis es all the runes, output "\textbf{RUNES UNSATISFIABLE! TRY ANOTHER GATE!}" \end{itemize}