Description

H正在和她的朋友在高原徒步，他们计划着从他们的营地A徒步到一个风景名胜B。

可惜的是，H有了点高原反应。请你帮助他们找到一条路线，使该路线的最高高度尽可能小。 （$1:10^5$）

Input Format

输入数据包含整个$10^6 \times 10^6$的的完整信息，格式如下：

第一行包含了一个整数$n$，表示着这个空间内的三角形的数量。接下来的$n$行，每行包含九个整数，分别是 $x_{i_1},y_{i_1},z_{i_1},x_{i_2},y_{i_2},z_{i_2},x_{i_3},y_{i_3},z_{i_3}$ ，是一个三角形的坐标。每个三角形的坐标都在区间[$0, 10^6$]之间。最后两行分别包含了A处的坐标和B处的坐标。

给定的三角形保证在一个一致的坐标系。三角形在XY平面上的投影是非简并的，并且填充正方形而不重叠。一个三角形的顶点永远不会位于另一个三角形的边内。A点和B点属于同一个坐标系，且两者不同位置。

Output Format

输出从A到B的路线，其最高高度可能最小。第一行应包含m，即此多段线中的顶点数。下面的每m条线都应该包含多段线顶点的三个整数坐标。

顶点必须沿路线列出，从A到B（包括这两个端点）。 路线顶点的所有坐标都应为整数。每个多段线边必须属于输入文件（可能是其边）中的某个三角形。路线的拐点数不能超过5n。

8
1000000 0 0 1000000 1000000 150000 600000 600000 400000
0 1000000 0 600000 600000 400000 600000 1000000 300000
0 1000000 0 400000 300000 150000 600000 600000 400000
400000 0 200000 1000000 0 0 400000 300000 150000
400000 300000 150000 1000000 0 0 600000 600000 400000
600000 600000 400000 1000000 1000000 150000 600000 1000000 300000
0 0 0 400000 0 200000 400000 300000 150000
0 1000000 0 0 0 0 400000 300000 150000
100000 700000 37500
900000 400000 137500

4
100000 700000 37500
400000 300000 150000
900000 150000 100000
900000 400000 137500