Ввод
В недавнем конкурсе по программированию одна из задач касалась укладки полов прямоугольными плитками. Спецификация ввода выглядит следующим образом:
Ввод содержит несколько полов. Первая строка ввода указывает количество полов. Каждый пол описывается в нескольких строках. Первая строка содержит два положительных целых числа: длину и ширину пола в миллиметрах. Пол имеет длину или ширину не более 40 000 мм. Следующая строка содержит одно число: количество t плиток (1 ≤ t ≤ 100). Следующие t строк содержат описание плитки. Плитка задается четырьмя целыми числами:
xl yl xh yh
где (xl, yl) — координаты нижнего левого угла плитки, а (xh, yh) — координаты верхнего правого угла плитки. Плитка всегда имеет положительную площадь. Порядок координат пола и плитки совпадает. Можно предположить, что плитки не пересекаются и покрывают пол, весь пол и только пол. Последняя строка этой спецификации вызвала некоторые проблемы. Не для участников, а для судей. Некоторые тестовые случаи состоят из множества плиток. Как мы можем быть уверены, что наш файл ввода соответствует этому условию? Нам нужна проверочная программа, которая проверяет это условие.
Задача
Дан файл ввода в указанном выше формате, выясните для каждого пола, соответствуют ли плитки следующим условиям:
не пересекаются,
не выходят за пределы пола,
покрывают пол.
Входные данные
Ввод содержит несколько полов. Первая строка ввода указывает количество полов. Каждый пол описывается в нескольких строках. Первая строка содержит два положительных целых числа: длину и ширину пола в миллиметрах. Пол имеет длину или ширину не более 40 000 мм. Следующая строка содержит одно число: количество t плиток (1 ≤ t ≤ 100). Следующие t строк содержат описание плитки. Плитка задается четырьмя целыми числами:
xl yl xh yh
где (xl, yl) — координаты нижнего левого угла плитки, а (xh, yh) — координаты верхнего правого угла плитки. Плитка всегда имеет положительную площадь. Порядок координат пола и плитки совпадает.
Выходные данные
Для каждого пола вывод содержит одну строку, содержащую одно из следующих слов:
NONDISJOINT, если обнаружены пересекающиеся плитки;
NONCONTAINED, если пересекающихся плиток нет, но некоторые плитки выходят за пределы пола;
NONCOVERING, если пересекающихся плиток нет, и плитки не выходят за пределы пола, но некоторые части пола не покрыты;
OK, если ни одно из этих условий не выполняется.