| Software Engineering Cup 2022 |
|---|
| Закончено |
Влад подготовил абсолютно новый проект корпуса для Факультета Вычислительной Техники. Согласно ему, здание будет парить в воздухе, благодаря современным технологиям строительства.
Однако почти сразу же эйфорию Влада нарушили $$$n$$$ архитектурных отделов организации ПанамГорстройУправление. Каждое из них выставило установку на то, в какой зоне города можно строить объект.
Каждая из зон представляет собой Кубоид — трехмерную фигуру, у которой шесть граней, являющихся прямоугольниками.
Несмотря на недовольство, Влад обязан удовлетворить требования всех отделов, хотя зданию он хотел бы отдать как можно больше места, причем объем под строительство должен быть ненулевым.
Первая строка входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество установок.
Следующие $$$n$$$ строк содержат шесть целых чисел $$$x_1$$$, $$$y_1$$$, $$$z_1$$$, $$$x_2$$$, $$$y_2$$$, $$$z_2$$$ ($$$-10^9 \le x_1, y_1, z_1, x_2, y_2, z_2 \le 10^9$$$, $$$x_1 \lt x_2$$$, $$$y_1 \lt y_2$$$, $$$z_1 \lt z_2$$$) — описание двух углов $$$(x_1, y_1, z_1)$$$ и $$$(x_2, y_2, z_2)$$$ кубоида, внутри которого можно построить здание.
Выведите шесть чисел $$$x_s$$$, $$$y_s$$$, $$$z_s$$$, $$$x_e$$$, $$$y_e$$$, $$$z_e$$$ — описание двух углов $$$(x_s, y_s, z_s)$$$ и $$$(x_e, y_e, z_e)$$$ кубоида наибольшего объема, внутри которого можно построить здание. Учтите, что должны выполняться неравенства $$$x_s \lt x_e$$$, $$$y_s \lt y_e$$$, $$$z_s \lt z_e$$$. Выведите «PROHIBITED» (без кавычек), если невозможно построить здание, не нарушая установок.
2 0 0 0 2 2 2 1 1 1 3 3 3
1 1 1 2 2 2
3 -2 0 -1 3 4 0 -1 2 -2 2 5 0 -4 1 -1 3 3 1
-1 2 -1 2 3 0
2 -2 -2 -2 -1 -1 -1 1 1 1 2 2 2
PROHIBITED
Графическое представление первого примера изображено на рисунке $$$1$$$
Рисунок 1
