로봇 충돌

xy평면 위에 반지름이 $r$인 원 모양 로봇 $n$대가 서로 겹치지 않게 놓여 있다. 시각 0에 모든 로봇이 동시에 출발한다. 각 로봇의 속도는 $(v_x, v_y)$와 $(-v_x, -v_y)$ 중 하나이고, 로봇은 방향을 바꾸지 않고 계속 직진한다.

두 로봇의 중심 사이 거리가 $2r$보다 가까워지면 두 로봇이 충돌한 것이다. 충돌이 일어나는지 판정하고, 일어난다면 가장 이른 충돌 시각, 즉 어떤 두 중심 사이 거리가 처음으로 $2r$이 되는 시각을 구하라.

입력은 여러 개의 데이터셋으로 이루어진다. 각 데이터셋의 형식은 다음과 같다.

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

$n$은 로봇의 수다 ($2 \le n \le 100000$). $(v_x, v_y)$는 속도 벡터이고, $v_x$와 $v_y$는 모두 $-1$ 이상 $1$ 이하다. $r$은 로봇의 반지름이며 양의 실수다. $(rx_i, ry_i)$는 $i$번 로봇 중심의 좌표이고, 모든 좌표는 $-1200$ 이상 $1200$ 이하다. $u_i$가 $1$이면 $i$번 로봇은 속도 $(v_x, v_y)$로, $-1$이면 $(-v_x, -v_y)$로 움직인다.

모든 로봇 쌍은 다음 세 조건을 만족한다.

• 시각 0에서 두 중심 사이 거리가 $2r + 10^{-8}$보다 가깝지 않다.
• 충돌하는 쌍이면 두 중심 사이 거리가 어느 순간 $2r - 10^{-8}$보다 작아진다.
• 충돌하지 않는 쌍이면 두 중심 사이 거리가 항상 $2r + 10^{-8}$ 이상이다.

모든 데이터셋의 $n$을 더한 값은 200000 이하다. 충돌이 일어나는 데이터셋에서 가장 이른 충돌 시각은 $10^6$ 미만이다. 입력의 마지막 줄에는 0 하나만 주어지며, 이 줄은 처리하지 않는다.

각 데이터셋마다 한 줄씩 출력한다. 충돌하는 쌍이 있으면 가장 이른 충돌 시각을 소수점 아래 여섯째 자리까지 반올림해 출력하고, 소수점 아래 여섯 자리를 모두 적는다. 충돌하는 쌍이 하나도 없으면 SAFE를 출력한다.