Rain

In recent years, hurricanes and tsunamis have shown the destructive power of water. That power is not limited to the sea. Heavy rain can cause floods that destroy houses and fields. Scientists use detailed models to predict where water will collect after a heavy rain.

One way to model a hilly landscape is triangulation, which approximates a surface with triangles. Each side of a triangle is shared by two adjacent triangles, except for triangles on the region boundary, which may have some sides that are not shared.

Suppose you have a triangulation model of a landscape. Rain starts to fall. Some water flows into the sea, and the rest is trapped by the landscape and forms lakes. Your task is to find how many lakes form and the water level of each one. Assume the rain is heavy enough to fill every lake up to its maximal level.

For any lake, you can sail a boat of arbitrarily small but nonzero size between any two points on its surface, excluding the boundary. So if two lakes share only one point, or only points with zero depth, they are different lakes.

The input contains several test cases. Each test case starts with a line containing two integers $p \ge 3$, the number of points, and $s \ge 3$, the number of sides of the triangulation. Each of the next $p$ lines describes one point. It starts with a two-letter code that is unique within the test case, followed by three integers $x$, $y$, and $h$. Here $-10000 \le x, y \le 10000$ are the planar coordinates and $0 \le h \le 8848$ is the height above sea level.

Each of the next $s$ lines describes one side by giving its two endpoints as two different two-letter codes. When the sides are projected onto the xy-plane, these conditions hold:

• No side intersects another side except at its endpoints.
• The points and sides form a triangulation of a single connected region.
• The region has no holes, so its boundary is one closed polygonal curve.

Points outside the region are lower than the closest point on the boundary. Water that reaches the boundary flows out freely.

The last line of the input contains two zeroes.

For each test case, print the case number, then the water level of every distinct lake inside the region, one per line, in non-decreasing order. Levels are heights above sea level. If no lake forms, print a single 0 on its own line. Follow the output format exactly.