Hiking in the Hills

Input

Contains full information about the landscape of a square region 10^6 \times 10^6 in the following format. The first line contains integer $n$ - the number of triangles in the landscape (2 \leq n \leq 2000). Each of following $n$ lines contains nine integers 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} - coordinates of a triangle. All coordinates belong to the closed interval [$0$, 10^6]. The two last lines contain three integers each: x_A, y_A, z_A and x_B, y_B, z_B - coordinates of the camp $A$ and the showplace $B$.

The given triangles are guaranteed to describe a consistent continuous landscape. Projections of triangles onto $XY$ plane are non-degenerate and fill the square without overlapping. A vertex of one triangle never lays inside an edge of another triangle. Points $A$ and $B$ belong to the landscape surface and are different.

Output

Output a polyline route from $A$ to $B$ with the smallest possible topmost height. The first line should contain $m$, the number of vertices in this polyline. Each of following $m$ lines should contain three integer coordinates of a polyline vertex: x_i, y_i and z_i. Vertices must be listed along the polyline, from $A$ to $B$ (including these two endpoints).

All coordinates of polyline vertices should be integer. Each polyline edge must belong to some triangle from the input (possibly, to its edge). The number of vertices in the polyline must not exceed $5n$.

Examples