반지와 룬

프로도가 모리아 광산에 들어서서 여러 개의 관문을 마주쳤다. 각 관문에는 그 관문을 제어하는 특수한 반지들의 상태를 묘사하는 고대의 수수께끼가 새겨져 있다. 프로도는 이 수수께끼를 살펴 관문을 열 수 있는지, 아니면 그저 죽음의 함정인지 판단해야 한다.

하나의 수수께끼는 여러 개의 룬으로 이루어진다. 올바른 룬은 서로 다른 3개의 반지에 관한 정확히 3개의 진술로 구성된다. 각 진술은 특정 반지가 회전 중인지(spinning) 멈춰 있는지에 따라 참 또는 거짓이 된다. 하나의 수수께끼가 관문을 제어하는 모든 반지를 반드시 사용할 필요는 없다.

관문을 열려면 호빗들은 어떤 반지를 회전시키고 어떤 반지를 그대로 둘지 정한 뒤 주문을 왼다. 수수께끼 전체가 만족될 때에만, 즉 모든 룬이 적어도 하나의 참인 진술을 가질 때에만 관문이 열린다.

표기법: 각 진술은 부호가 있는 반지 번호로 적는다. 양수 $r$은 반지 $r$이 회전 중일 때 참이고, 음수 $-r$은 반지 $r$이 회전하지 않을 때 참이다. 예를 들어 룬 1 -2 3 0은 (반지 1이 회전 중) OR (반지 2가 회전하지 않음) OR (반지 3이 회전 중)일 때 참이다. 끝의 0은 룬의 끝을 나타낸다. 하나의 룬 안에서 같은 반지는 최대 한 번만 나타날 수 있지만, 서로 다른 룬에서는 같은 반지를 여러 번 사용할 수 있다.

• 첫째 줄에는 관문의 수를 나타내는 정수 $g$ ($1 \le g \le 30$)가 주어진다.
• 각 관문의 첫째 줄에는 두 정수 rings ($3 \le \text{rings} \le 22$)와 runes ($1 \le \text{runes} \le 100$)가 공백으로 구분되어 주어진다. 반지는 $1$번부터 rings번까지 번호가 매겨지며, 수수께끼가 모든 반지를 사용할 필요는 없다.
• 이어지는 runes개의 줄에는 각 룬이 공백으로 구분된 네 정수 $r_1\ r_2\ r_3\ 0$으로 주어진다. 세 진술은 $r_1, r_2, r_3$(각각 부호 있는 32비트 정수)이며, 끝의 $0$은 룬의 종료를 나타낸다.

각 관문마다 정확히 한 줄을 출력한다. 어떤 룬에 오류가 있으면, 다음 우선순위에 따라 가장 높은 우선순위의 오류 하나만 출력한다.

1. 어떤 룬이든 널 반지(값이 $0$ 또는 $-0$인 진술)를 포함하면 수수께끼 전체가 무효다. INVALID: NULL RING을 출력한다.
2. 그렇지 않고, 어떤 룬이든 $r < -\text{rings}$ 또는 $r > \text{rings}$인 진술 $r$을 포함하면 INVALID: RING MISSING을 출력한다. (널 반지가 있는 경우에는 이 오류를 출력하지 않는다.)
3. 그렇지 않고, 어떤 하나의 룬이 같은 반지를 두 번 이상 가리키면(예: -2 2 3 0 또는 3 1 1 0) INVALID: RUNE CONTAINS A REPEATED RING을 출력한다.
4. 그 외에는 수수께끼가 올바른 형식이다. 완전히 동일한 룬이 반복되면 하나로 취급한다. 회전/정지 반지의 어떤 배치가 모든 룬을 만족시키면 RUNES SATISFIED!를, 어떤 배치로도 모든 룬을 만족시킬 수 없으면 RUNES UNSATISFIABLE! TRY ANOTHER GATE!를 출력한다.