A new system for preventing airplane collisions is installed at
the Koltsovo airport. The system traces all flying objects within
a certain radius of action: airplanes, helicopters, parachutists, etc.
It is assumed that objects move in straight lines with
constant speeds, and their motions are calculated according to this
model. If the distance between two objects becomes equal to some
critical value d, the system gives an alarm. You are given
coordinates and velocities of objects. Determine the pair that will first
cause an alarm.
In the first line you are given the number n (at most 500)
of objects within the range of the system and the critical
distance d (from 0.1 to 10000).
Each of the following n lines contains the current coordinates
(x, y, z) and the velocity components
(vx, vy, vz) of a flying object.
The absolute values of coordinates do not exceed 10000, and the absolute
values of velocity do not exceed 100. At the initial moment, the
objects are at safe distances from each other.
If there will be an alarm, then output "ALARM!" in the first line.
The second line must contain the time t of the first alarm (up to
the third fractional digit) and the numbers of the objects at the critical distance
from each other at that moment a and b;
the initial time moment is 0.
If at the moment t there are several pairs of objects at the
critical distance, then output any of them.
The objects are enumerated from 1 to n in the order in which they are given in
the input. If there are no alarms, output "OK".
1.0 1.0 -1.0 0.0 0.0 10.0
0.0 0.0 4.0 2.0 0.0 0.0
0.500 1 2
Problem Author: Vladimir Yakovlev
Problem Source: IX USU Open Personal Contest (March 1, 2008)