Задачі
Цепи & Ко.
Цепи & Ко.
Цепи & Ко специализируется в производстве бесконечно прочных цепей. Из-за своей продукции высокого качества они быстро завоевывают рынок. Это приводит к новым вызовам, о которых они не могли даже думать раньше. Как например автоматическая проверка надежности звеньев при помощи компьютерной программы, которую Вам следует написать.
Компания производит звенья одинакового размера. Каждое звено представляет собой бесконечно тонкую квадратную рамку в трех измерениях (сделана из четырех бесконечно тонких сегментов).
Во время тестирования все звенья являются выровненными по осям^1 и расположены так, что никакие две рамки не пересекаются. Чтобы совершить качественное испытание на прочность, два множества звеньев \textbf{A} и \textbf{B} сковываются таким образом, что каждое звено \textbf{A} неразрывно связывается с каждым звеном из \textbf{B }("неразрывно" означает что звенья нельзя отделить друг от друга не разорвав одно из них).
Вы наткнулись на некоторые звенья (выровненными по осям, попарно непересекающимися). Находятся ли они в правильном положении для тестирования? Другими словами, можно ли их разбить на два непустых множества \textbf{A} и \textbf{B }с требуемым свойством?
________________________
^1Выровненный по осям означает что все сегменты параллельны одной из осей \textbf{X}, \textbf{Y} или \textbf{Z}.
\InputFile
Первая строка содержит количество тестов \textbf{t}. Структура каждого теста следующая:
Перед каждым тестом идет пустая строка. За ней следует строка с количеством звеньев \textbf{n }(\textbf{1 }≤ \textbf{n }≤ \textbf{10^6}) в цепи. Каждая из следующих \textbf{n }строк содержит \textbf{6 }целых чисел \textbf{x_i}, \textbf{y_i}, \textbf{z_i}, \textbf{x'_i}, \textbf{y'_i}, \textbf{z'_i}, все между \textbf{-10^9} и \textbf{10^9} - координаты двух противоположных углов \textbf{i}-го звена.
\OutputFile
Для каждого теста вывести в отдельной строке слово \textbf{YES}, если множество звеньев находится в правильном положении для тестирования, и \textbf{NO }иначе.
Вхідні дані #1
3 2 0 0 0 0 10 10 -5 5 15 5 5 25 5 0 0 0 0 10 10 -5 5 6 5 5 16 -5 5 -6 5 5 4 -5 6 5 5 16 5 -5 -6 5 5 4 5 3 0 0 0 3 0 -3 1 -1 -1 1 2 -4 -1 -2 -2 2 1 -2
Вихідні дані #1
NO YES YES