Problem: Prof. Jenifer A. Gibson is carrying out experiments with many robots. Since those robots are expensive, she wants to avoid their crashes during her experiments at her all effort. So she asked you, her assistant, as follows.

“Suppose that we have n (2 ≤ n ≤ 100000) robots of the circular shape with the radius of r, and that they are placed on the xy-plane without overlaps. Each robot starts to move straight with a velocity of either v or -v simultaneously, say, at the time of zero. The robots keep their moving infinitely unless I stop them. I’d like to know in advance if some robots will crash each other. The robots crash when their centers get closer than the distance of 2r. I’d also like to know the time of the first crash, if any, so I can stop the robots before the crash. Well, could you please write a program for this purpose?”



Input

The input consists of multiple datasets. Each dataset has the following format:


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


n is the number of robots. (vx, vy) denotes the vector of the velocity v. r is the radius of the robots. (rxi , ryi ) denotes the coordinates of the center of the i-th robot. ui denotes the moving direction of the i-th robot, where 1 indicates the i-th robot moves with the velocity (vx , vy), and -1 indicates (-vx , -vy).

All the coordinates range from -1200 to 1200. Both vx and vy range from -1 to 1.

You may assume all the following hold for any pair of robots:

* they must not be placed closer than the distance of (2r + 10-8 ) at the initial state;
* they must get closer than the distance of (2r - 10-8 ) if they crash each other at some point of time; and
* they must not get closer than the distance of (2r + 10-8 ) if they don’t crash.



The input is terminated by a line that contains a zero. This should not be processed.

Output

For each dataset, print the first crash time in a line, or “SAFE” if no pair of robots crashes each other. Each crash time should be given as a decimal with an arbitrary number of fractional digits, and with an absolute error of at most 10-4.

Example

Input

2
1.0 0.0
0.5
0.0 0.0 1
2.0 0.0 -1
2
1.0 0.0
0.5
0.0 0.0 -1
2.0 0.0 1
0


Output

0.500000
SAFE

Solution (in CPP):

Solution:
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 100000;

const double INF = 1e70;

/* typedef */

template <typename T>
struct Pt {
  T x, y;

  Pt() {}
  Pt(T _x, T _y) : x(_x), y(_y) {}
  Pt(const Pt& pt) : x(pt.x), y(pt.y) {}

  bool operator==(const Pt pt) const { return x == pt.x && y == pt.y; }
  Pt<T> operator+(const Pt pt) const { return Pt<T>(x + pt.x, y + pt.y); }
  Pt<T> operator-() const { return Pt<T>(-x, -y); }
  Pt<T> operator-(const Pt pt) const { return Pt<T>(x - pt.x, y - pt.y); }
  Pt<T> operator*(T t) const { return Pt<T>(x * t, y * t); }
  Pt<T> operator/(T t) const { return Pt<T>(x / t, y / t); }
  T dot(Pt v) const { return x * v.x + y * v.y; }
  T cross(Pt v) const { return x * v.y - y * v.x; }
  Pt<T> mid(const Pt pt) { return Pt<T>((x + pt.x) / 2, (y + pt.y) / 2); }
  T d2() { return x * x + y * y; }
  double d() { return sqrt(d2()); }

  Pt<T> rot(double th) {
    double c = cos(th), s = sin(th);
    return Pt<T>(c * x - s * y, s * x + c * y);
  }

  bool operator<(const Pt& pt) const {
    return x < pt.x || (x == pt.x && y < pt.y);
  }

  void print(string format) {
    printf(("(" + format + ", " + format + ")\n").c_str(), x, y);
  }
  void print() { print("%.6lf"); }
};

typedef Pt<double> pt;

struct Robot {
  pt p;
  int drc;
  Robot() {}
  Robot(pt _p, int _drc) : p(_p), drc(_drc) {}
  bool operator<(const Robot& r0) const { return p.x < r0.p.x; }
};

typedef set<Robot> srbt;

/* global variables */

int n;
pt v;
double r;
Robot rbts[MAX_N];

/* subroutines */

bool lessy(const Robot& r0, const Robot& r1) { return r0.p.y < r1.p.y; }

/* main */

int main() {
  for (;;) {
    cin >> n;
    if (n == 0) break;

    cin >> v.x >> v.y >> r;

    double th = -atan2(v.y, v.x);
    pt v0 = v.rot(th);
    //v0.print(); printf("th=%.6lf\n", th);

    double rr = r * 2;
    double dvx = v0.x * 2;
    
    for (int i = 0; i < n; i++) {
      pt p;
      cin >> p.x >> p.y >> rbts[i].drc;
      rbts[i].p = p.rot(th);
    }
    sort(rbts, rbts + n, lessy);
    
    double min_t = INF;
    srbt srl, srr;
    
    for (int i0 = 0, i1 = 0; i1 < n; i1++) {
      Robot& r1 = rbts[i1];

      while (i0 < i1 && r1.p.y - rbts[i0].p.y > rr) {
	if (rbts[i0].drc > 0) srl.erase(rbts[i0]);
	else srr.erase(rbts[i0]);
	i0++;
      }
      
      if (r1.drc < 0) {
	if (! srl.empty()) {
	  srbt::iterator rit = srl.lower_bound(r1);
	  if (rit != srl.begin()) {
	    rit--;
	    pt dp = r1.p - rit->p;
	    double t = (dp.x - sqrt(rr * rr - dp.y * dp.y)) / dvx;
	    if (min_t > t) min_t = t;
	  }
	}

	srr.insert(r1);
      }
      else {
	if (! srr.empty()) {
	  srbt::iterator rit = srr.lower_bound(r1);
	  if (rit != srr.end()) {
	    pt dp = rit->p - r1.p;
	    double t = (dp.x - sqrt(rr * rr - dp.y * dp.y)) / dvx;
	    if (min_t > t) min_t = t;
	  }
	}

	srl.insert(r1);
      }
    }

    if (min_t >= INF)
      cout << "SAFE" << endl;
    else 
      printf("%.6lf\n", min_t);
  }

  return 0;
}