Hiking in the Hills

Helen is hiking with her friends in a highland. The plan is to walk from their camp A to a lookout B.

Helen has started to feel dizzy from altitude sickness. Help the group find a route whose highest point is as low as possible.

The landscape is given as a set of triangles. A route is a polyline from A to B in which every segment lies entirely inside one of those triangles, so the route never leaves the surface. The topmost height of a route is the largest $z$ coordinate of any point on it. Find the smallest topmost height over all routes from A to B.

The landscape covers a square region of size $10^6 \times 10^6$.

The first line contains one integer $n$, the number of triangles in the landscape ($2 \le n \le 2000$).

Each of the next $n$ lines contains nine integers $x_{i1}$, $y_{i1}$, $z_{i1}$, $x_{i2}$, $y_{i2}$, $z_{i2}$, $x_{i3}$, $y_{i3}$, $z_{i3}$, the coordinates of one triangle. Every coordinate belongs to the closed interval $[0, 10^6]$.

The last two lines contain three integers each: $x_A$, $y_A$, $z_A$ and $x_B$, $y_B$, $z_B$, the coordinates of camp A and lookout B.

The triangles describe one consistent continuous landscape. Their projections onto the XY plane are non-degenerate and fill the square without overlapping. A vertex of one triangle never lies inside an edge of another triangle. A and B lie on the landscape surface and are different points.

Print one integer, the smallest topmost height that a route from A to B can have.