Кольца и Руны
Фродо вошел в шахты Мории и наткнулся на ряд ворот. На каждом из них была написана древняя загадка, описывающая состояние набора особых колец, которые контролируют эти ворота. Изучив загадку, Фродо может определить, можно ли открыть ворота или это просто смертельная ловушка.
Загадки состоят из множества рун. Каждая действительная руна содержит ровно 3 утверждения о 3 различных кольцах. Каждое утверждение в руне может быть истинным или ложным, в зависимости от состояния (вращается или не вращается) конкретного кольца в наборе колец, контролирующих ворота. Загадка для конкретных ворот не обязана использовать все возможные кольца, содержащиеся в наборе управления воротами.
Чтобы открыть ворота, хоббиты должны прочитать загадку, затем решить, какие из колец вращать, а какие оставить в покое. Как только они заставят вращаться правильные кольца, они произносят заклинание, и если вся загадка для ворот будет выполнена, ворота откроются. Для этого в каждой руне загадки должно быть хотя бы одно истинное утверждение.
Например, рассмотрим конкретную руну: 1 -2 3 0. Эта руна будет истинной, если (кольцо 1 вращается) ИЛИ (кольцо 2 НЕ вращается) ИЛИ (кольцо 3 вращается). (ПРИМЕЧАНИЕ: 0 указывает на конец руны, и хотя бы одно из утверждений в этой руне должно быть истинным, чтобы эта конкретная руна была истинной.) Если номер кольца в руне отрицательный (например, -2), это означает, что кольцо 2 должно НЕ вращаться, чтобы это конкретное утверждение в руне было истинным. Если номер кольца положительный (например, 3), это означает, что кольцо 3 ДОЛЖНО вращаться, чтобы это утверждение в руне было истинным. Конкретное кольцо может появляться только один раз в конкретной руне, однако кольцо может использоваться несколько раз во всей загадке, но не в одной и той же руне!
Входные данные
Входные данные будут состоять из следующего:
Первая строка входных данных содержит одно целое число g (где 1 ≤ g ≤ 30), которое обозначает количество ворот с загадками, которые нужно расшифровать.
Первая строка для каждого ворот содержит два целых числа, rings (где 3 ≤ rings ≤ 22) и runes (где 1 ≤ runes ≤ 100), разделенные пробелом. rings — это количество колец в управляющем наборе; каждое кольцо пронумеровано от 1 до rings, и загадки не обязаны использовать каждое возможное кольцо. runes — это количество рун, которые должны быть выполнены набором колец.
Следующие runes строк описывают отдельные руны, которые определяют отношения между кольцами для этих ворот. Каждая руна представлена одной строкой, содержащей четыре числа: r_1, r_2, r_3 и 0, где каждое из этих чисел разделено пробелом. Первые три числа — это 32-битные целые числа.
Выходные данные
Каждые ворота содержат ровно одну загадку (состоящую из нескольких рун), и ваш алгоритм должен выводить ровно одну строку для каждого ворот. Если одна или несколько рун в загадке содержат ошибки, выводите только ошибку с самым высоким приоритетом для этой загадки. Приоритет ошибок описан ниже:
Если ЛЮБАЯ руна в загадке содержит утверждение о нулевом кольце, например, 0 или -0, это самая серьезная ошибка в загадке, и вся загадка недействительна. Выведите "INVALID: NULL RING" как ошибку с самым высоким приоритетом.
Если ЛЮБАЯ руна в загадке содержит утверждение r или -r, где (r < -rings) или (r > rings), то это ВТОРАЯ по серьезности ошибка в загадке, и поэтому выведите "INVALID: RING MISSING". ПРИМЕЧАНИЕ: Не выводите это сообщение, если загадка содержала НУЛЕВОЕ кольцо!
Если ЛЮБАЯ отдельная руна ссылается на одно и то же кольцо более одного раза (например, -2 2 3 0 ИЛИ 3 1 1 0), это ТРЕТЬЯ по серьезности ошибка, поэтому выведите "INVALID: RUNE CONTAINS A REPEATED RING". Опять же, не выводите это сообщение, если где-то в загадке произошла ошибка с более высоким приоритетом.
Загадки могут содержать повторяющиеся руны. Рассматривайте все эти повторяющиеся руны как одну руну; поскольку они идентичны, если одна из них истинна, все повторяющиеся руны будут истинными.
Если существует конфигурация вращающихся/неподвижных колец, которая удовлетворяет все руны в загадке, выведите "RUNES SATISFIED!"
Если не существует возможной конфигурации вращающихся/неподвижных колец, которая удовлетворяет все руны, выведите "RUNES UNSATISFIABLE! TRY ANOTHER GATE!"