16853번 - 필름

고고학자 류트는 유적지 발굴 도중 외계 행성 rdd-6584에 사는 외계인의 흔적으로 보이는 기록을 발견하였다. 류트는 다른 기록과 이 기록을 대조하던 도중 이 기록이 특수 필름에 대한 실험 결과라는 것을 알게 되었다. 기록에 따르면 이 필름은 여러 색이 있으며, 삼원색으로만 구성된다는 것을 알게 되었다. 따라서 필름의 색은 빨간색, 초록색, 파란색의 세 단색광의 유무로 표현 가능하며 총 8가지가 존재하게 된다.

류트는 이 필름 n개에 대해 실험한 실험 기록 m개를 찾았다. 필름은 1번부터 n번까지 번호가 붙여져 있다. 하나의 실험은 두 필름을 겹친 뒤 특정한 파장의 빛을 쏘여 어떤 색깔이 나타나는지 관측하는 것으로 이루어진다. 쏘는 빛은 하나 이상의 단색광의 합으로 이루어진다. 특이하게도 이 필름은 파장에 따라 관측되는 색이 달라진다. 만약 기준보다 높은 파장의 빛을 쏜다면, 그 빛이 가지고 있는 각 단색광마다 두 필름이 모두 그 단색광을 가지고 있어야만 그 단색광을 반사할 것이다. 반대로 기준보다 낮은 파장의 빛을 쏜다면, 그 빛이 가지고 있는 각 단색광마다 두 필름 중 하나 이상이 그 단색광을 가지고 있어야만 그 단색광을 반사할 것이다. 관측되는 색은 반사되는 모든 단색광의 합집합과 같다.

류트는 이 실험 기록이 정말로 외계인이 실험한 기록인지, 아니면 그저 낙서일 뿐인지를 판별하려고 한다. 류트는 다음 조건을 만족하는 실험 기록을 외계인의 실험 기록이라고 하기로 했다.

• 모든 실험에는 오류가 없어야 한다. 따라서 파장에 따라 반사되는 빛이 위에 서술된 바와 일치하도록 모든 필름의 색을 정할 수 있는 경우가 하나 이상 존재한다.

실험 기록이 주어질 때, 류트는 이 실험 기록이 외계인의 것인지, 또는 낙서일 뿐인지 판단하고 싶다. 류트를 도와주자.

첫 번째 줄에 필름의 개수 n(1 ≤ n ≤ 50,000) 과 실험 기록의 개수 m(1 ≤ m ≤ 200,000)이 공백을 사이에 두고 주어진다.

두 번째 줄부터 m+1번째 줄 까지 A B K C₁ C₂ 형태로 실험 기록이 주어진다.

A는 첫 번째 필름의 번호, B는 두 번째 필름의 번호를 뜻한다. (1 ≤ A, B ≤ n) K는 파장의 높낮이로 기준보다 높으면 H, 낮으면 L이 주어진다. C₁과 C₂는 각각 쏜 빛과 관측한 빛의 색깔이다. C₁과 C₂는 표에서 주어진 색 이름 중 하나이다. C₁은 조건에 따라 절대 BLACK이 되지 않음에 유의하라. 

외계인의 실험 기록이라면 “ALIEN”을, 그렇지 않다면 “THINKINGFACE”을 출력한다.