Елена путешествует со своими друзьями в высокогорье. Их план состоит в том, чтобы отправиться из своего лагеря A в прекрасное место B.

К сожалению, у Елены началось головокружение из-за высотной болезни. Помогите ее группе найти такой маршрут, чтобы максимальная высота на нем была как можно меньше.

Входные данные

Содержит полную информацию о ландшафте квадратного региона 106 * 106 в следующем формате. Первая строка содержит количество треугольников в ландшафте n (2 ≤ n ≤ 2000). Каждая из следующих n строк содержит девять целых чисел xi1, yi1, zi1, xi2, yi2, zi2, xi3, yi3, zi3 - координаты треугольника. Все координаты принадлежат интервалу [0, 106]. Каждая из двух последних строк содержит три целых числа xA, yA, zA и xB, yB, zB - координаты лагеря A и прекрасного места B.

Заданные треугольники гарантированно описывают согласованный непрерывный ландшафт. Проекции треугольников на плоскость XY невырождены и заполняют квадрат без перекрытия. Вершина одного треугольника никогда не лежит внутри края другого треугольника. Точки A и B принадлежат поверхности ландшафта и различны.

Выходные данные

Вывести маршрут в виде ломаной от A до B с наименьшей наивысшей точкой. В первой строке вывести количество вершин в ломаной m. В каждой из следующих m строк вывести три целых чиса - координаты вершины ломаной: xi, yi и zi. Вершины следует вывести в порядке их расположения на ломаной, от A до B (включая эти две точки).

Все координаты вершин ломаной должны быть целыми. Каждый отрезок ломаной должен принадлежать некоторому входному треугольнику (возможно стороне треугольника). Количество вершин в ломаной не должно превышать 5n.