Go Go Gorelians

Interview

Time limit1sMemory limit128 MB

Summary

Build the network by linking each new planet to the nearest existing planet, then find the planet or two adjacent planets that minimize the maximum distance to all others.

Level: Medium6 of 10
Topics: Graph, Tree, BFS, Geometry
Solved: No attempts yet

Problem

The Gorelians travel through space using warp links. Travel through a warp link is instantaneous, but for safety reasons an individual can warp only once every 10 hours. The cost of building a warp link grows in direct proportion to the straight-line distance between the two endpoints of the link.

The Gorelians, the dominant force in the known universe, are often bored, so they frequently conquer new regions of space in the following way.

The initial invasion force finds a suitable planet and conquers it, establishing a Regional Gorelian Galactic Government (RGGG) that governs all Gorelian affairs in that region of space.
When the next planet is conquered, a single warp link is built between the new planet and the RGGG planet. Planets connected by warp links in this way form the Regional Gorelian Planetary Network (RGPN).
As more planets are conquered, each new planet is joined by a single warp link to the nearest planet already in the RGPN, keeping the cost of adding new planets to a minimum. If two or more planets are equally close to the new planet, the new planet is linked to whichever of them was conquered first.

This creates a problem, however. Because planets are conquered in a more or less random order, after a while the RGGG is probably not in an ideal location. Some Gorelians who need to consult the RGGG may need only one or two warps, while others may need dozens — very inconvenient given the 10-hour wait between warps.

So, once every Gorelian year, the RGGG analyzes the RGPN and relocates to an optimal location. The optimal location is defined as a planet that minimizes the maximum number of warps required to reach the RGGG from any planet in the RGPN. As it turns out, there is always exactly one or two such planets. When there are two, they are always directly adjacent via a warp link, and the RGGG divides itself evenly between the two planets.

Your task is to write a program that finds the optimal planet or planets for the RGGG. For this problem, the region of space conquered by the Gorelians is a cube ranging from $(0, 0, 0)$ to $(1000, 1000, 1000)$ .

Input

The input consists of several scenarios, each independent, in which the Gorelians conquer a region of space. The first line of a scenario is an integer $N$ , the total number of planets conquered. The next $N$ lines give, in the order the planets were conquered, the ID and coordinates of each planet added to the RGPN, in the format ID X Y Z. An ID is an integer from 1 to 1000. $X$ , $Y$ , and $Z$ are integers from 0 to 1000. The numbers on a line are separated by a single space. A line containing $N = 0$ marks the end of the input.

Output

For each scenario, output the ID or IDs of the optimal planet(s) to which the RGGG should relocate. For a single planet, output that planet's ID. For two planets, output both IDs, smallest ID first, separated by a single space.

Examples1

Example 1

Input

5
1 0 0 0
2 0 0 1
3 0 0 2
4 0 0 3
5 0 0 4
5
1 0 0 0
2 1 1 0
3 3 2 0
4 2 1 0
5 3 0 0
10
21 71 76 4
97 32 5 69
70 33 19 35
3 79 81 8
31 91 17 67
52 31 48 75
48 90 14 4
41 73 2 21
83 74 41 69
26 32 30 24
0

Expected output

3
2 4
31 97