INTERCEPTIONS IN THE AEGEAN

The Hellenic Air Force performs a multifaceted mission. During peacetime, it participates in a plethora of missions, including search and rescue, aeromedical evacuations, firefighting, and peacekeeping missions across the globe. However, its primary role is the defense of Greek airspace against violations. Almost daily, Greek fighter aircraft undertake missions for the identification and interception of foreign aircraft. In several instances, interceptions escalate into engagements. The conditions in these cases are particularly challenging for two main reasons: Fighter aircraft emit the minimum possible signal (across the entire radio frequency spectrum) to avoid easy detection, and they are generally of the same type as the adversary's aircraft.

Flight safety makes it imperative to have systems that assist in the control and management of airspace by relevant authorities. In this direction, the most crucial role is played by systems providing reliable and centralized situational awareness of their Flight Information Region (FIR). Systems for the identification of closer traces are of particular importance, aiming to provide timely information to operators about the status of the airspace within their area of responsibility. These systems must be able to recognize the nearest aircraft as quickly as possible.

Problem

Develop a program in one of the IOI languages that, after reading the output data of a digital radar in the form of a triplet of data corresponding to each detected trace, locates and marks the traces with the smallest distance between them, thus indicating the highest risk of collision.
(The sole criterion for detection is the minimum distance and not other factors such as the identity of the aircraft.)

Input Files

The input files named airforce.in are text files with the following structure: The first line contains an integer ~N~. ~10 \le N \le 1.000~, corresponding to the number of detected traces. The next ~N~ lines contain a triplet of numbers ~x, y, z~. (~-1.000 \le x, y, z \le 1.000~) corresponding to the three coordinates of a Cartesian system. The numbers are separated by a space.

Output Files

The output files named airforce.out are text files with the following structure: They consist of a single line containing two numbers separated by a space. The ascending numbers (positions ~n-1~ in the airforce.in file) of the traces that have the smallest distance between them.

Examples of Input - Output Files:

1ο

STDIN (airforce.in)

10
100 2 0
10 3 0
50 6 0
70 7 0
90 8 0
110 9 0
130 10 0
150 11 0
150 12 0
1 3 2

STDOUT (airforce.out)

8 9

2ο

STDIN (airforce.in)

15
1 1 1
1 1 2
1 2 3
1 2 4
1 2 5
1 3 6
1 3 7
1 4 8
1 4 9
1 5 11
1 5 13
1 6 15
1 6 17
1 7 18
1 7 20

STDOUT (airforce.out)

1 2

Notes:

1. Distance between two points in three-dimensional space is calculated as ~d = ((x2 - x1)^2 + (y2 - y1)^2 + (z2 - z1)^2)^{1/2}~.
2. The calculation time is crucial for aviation operations. Implementations with shorter time will have greater significance in case of ties.
3. The maximum distance at which two aircraft can be recognized is ~10.000~ distance units.
4. If the two closest aircraft are the 3rd and 4th, the file airforce.out will have the values [~3~ ~4~] and not [~4~ ~3~].
5. There are no more than one pair of aircraft with the same minimum distance between them.
6. Maximum execution time is ~5~ sec. Maximum allowable memory usage is ~5~ MB.