Helen 和她的朋友正在高地上徒步旅行。他们的计划是从营地 $A$ 徒步前往一个美丽的景点 $B$。

不幸的是，由于高原反应，Helen 开始感到头晕。请帮助她的小组找到一条路线，使得该路线上的最高海拔尽可能低。

(坐标轴缩放比例为 1 到 $10^5$)

输入格式

输入文件包含一个 $10^6 \times 10^6$ 的方形区域的完整地形信息，格式如下：第一行包含一个整数 $n$ —— 地形中三角形的数量 ($2 \le n \le 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$。

样例

输入 1

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

输出 1

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