Похід у гори
Єлена подорожує зі своїми друзями у високогір'ї. Їхній план полягає в тому, щоб вирушити з табору A до прекрасного місця B.
На жаль, у Єлени почалося запаморочення через висотну хворобу. Допоможіть її групі знайти такий маршрут, щоб максимальна висота на ньому була якомога меншою.
Вхідні дані
Містять повну інформацію про ландшафт квадратного регіону 10^6 * 10^6 у наступному форматі. Перший рядок містить кількість трикутників у ландшафті n (2 ≤ n ≤ 2000). Кожен з наступних n рядків містить дев'ять цілих чисел x[i1], y[i1], z[i1], x[i2], y[i2], z[i2], x[i3], y[i3], z[i3] - координати трикутника. Усі координати належать інтервалу [0, 10^6]. Кожен з двох останніх рядків містить три цілі числа x[A], y[A], z[A] і x[B], y[B], z[B] - координати табору A і прекрасного місця B.
Задані трикутники гарантовано описують узгоджений безперервний ландшафт. Проекції трикутників на площину XY невироджені та заповнюють квадрат без перекриття. Вершина одного трикутника ніколи не лежить всередині краю іншого трикутника. Точки A і B належать поверхні ландшафту і різні.
Вихідні дані
Виведіть маршрут у вигляді ламаної від A до B з найменшою найвищою точкою. У першому рядку виведіть кількість вершин у ламаній m. У кожному з наступних m рядків виведіть три цілі числа - координати вершини ламаної: x[i], y[i] і z[i]. Вершини слід вивести в порядку їх розташування на ламаній, від A до B (включаючи ці дві точки).
Усі координати вершин ламаної повинні бути цілими. Кожен відрізок ламаної повинен належати деякому вхідному трикутнику (можливо стороні трикутника). Кількість вершин у ламаній не повинна перевищувати 5n.