Robots' Crash

There are $n$ robots on the xy-plane. Each robot is a circle of radius $r$, and no two of them overlap at the start. At time 0 every robot starts moving at the same moment. The velocity of a robot is either $(v_x, v_y)$ or $(-v_x, -v_y)$, and a robot goes straight forever without changing direction.

Two robots crash when the distance between their centers becomes smaller than $2r$. Decide whether any crash happens, and if it does, report the earliest crash time, that is, the first moment at which the distance between some two centers equals $2r$.

The input consists of several datasets. Each dataset has this format:

n
vx vy
r
rx1 ry1 u1
rx2 ry2 u2
...
rxn ryn un

$n$ is the number of robots ($2 \le n \le 100000$). $(v_x, v_y)$ is the velocity vector, and both $v_x$ and $v_y$ are between $-1$ and $1$. $r$ is the radius of the robots and is a positive real number. $(rx_i, ry_i)$ is the center of robot $i$, and every coordinate is between $-1200$ and $1200$. If $u_i$ is $1$, robot $i$ moves with velocity $(v_x, v_y)$; if $u_i$ is $-1$, it moves with velocity $(-v_x, -v_y)$.

Every pair of robots satisfies these three conditions:

• at time 0 the distance between the two centers is at least $2r + 10^{-8}$;
• if the pair crashes, the distance between the two centers becomes smaller than $2r - 10^{-8}$ at some moment;
• if the pair never crashes, the distance between the two centers stays at least $2r + 10^{-8}$.

The sum of $n$ over all datasets is at most 200000. In a dataset where a crash happens, the earliest crash time is less than $10^6$. The last line of the input holds a single 0 and is not part of any dataset.

Print one line for each dataset. If some pair crashes, print the earliest crash time rounded to six digits after the decimal point, always writing all six digits. If no pair ever crashes, print SAFE.