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<set>
#include<cmath>
#include<cstdio>
#include<algorithm>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

const double INF=1e77;
const double PI=acos(-1);

template<class T>
struct point{ T x,y; };

template<class T>
double abs(const point<T> &a){ return sqrt(a.x*a.x+a.y*a.y); }

template<class T>
double arg(const point<T> &a,const point<T> &b){
	double ta=atan2(a.y,a.x);
	double tb=atan2(b.y,b.x);
	return tb-ta<0 ? tb-ta+2*PI : tb-ta;
}

point<double> rot(const point<double> &a,double theta){
	return (point<double>){a.x*cos(theta)-a.y*sin(theta),a.x*sin(theta)+a.y*cos(theta)};
}

struct robot{
	point<double> p; // 位置
	int dir; // 移動方向 (+1 or -1)
	bool operator<(const robot &Z)const{ return p.x<Z.p.x; }
};

// 速さ v で動くロボット A, B が衝突するときの時刻
double f(const robot &A,const robot &B,double r,double v){
	double w=abs(A.p.x-B.p.x);
	double h=sqrt(4*r*r-w*w);
	return (abs(A.p.y-B.p.y)-h)/(2*v);
}

int main(){
	for(int n;scanf("%d",&n),n;){
		point<double> v;
		double r; scanf("%lf%lf%lf",&v.x,&v.y,&r);
		double v_abs=abs(v);

		static robot Z[100000];
		rep(i,n) scanf("%lf%lf%d",&Z[i].p.x,&Z[i].p.y,&Z[i].dir);

		// y 軸の +/- 方向に移動するように座標を取り替える
		double theta=-arg((point<double>){0,1},v);
		v=rot(v,theta);
		rep(i,n) Z[i].p=rot(Z[i].p,theta);

		sort(Z,Z+n);

		double ans=INF;
		// S_u : 上方向に動くロボットの集合
		// S_d : 下方向に動くロボットの集合
		// double をそのまま比較しているけど、誤差が出るような演算はしていないので大丈夫
		set< pair<double,int> > S_u,S_d;
		for(int i=0,j=0;i<n;i++){
			// x 方向に離れすぎてロボット i とぶつかれなくなったロボットを削除
			while(j<i && Z[i].p.x-Z[j].p.x>2*r){
				if(Z[j].dir==1) S_u.erase(make_pair(Z[j].p.y,j));
				else            S_d.erase(make_pair(Z[j].p.y,j));
				j++;
			}

			set< pair<double,int> >::iterator it;
			// ロボット i は上方向に動く
			if(Z[i].dir==1){
				if(!S_d.empty()){
					it=S_d.lower_bound(make_pair(Z[i].p.y,-1));
					if(it!=S_d.end()){
						int k=it->second;
						ans=min(ans,f(Z[i],Z[k],r,v_abs));
					}
				}
			}
			// ロボット i は下方向に動く
			else{
				if(!S_u.empty()){
					it=S_u.lower_bound(make_pair(Z[i].p.y,-1));
					if(it!=S_u.begin()){
						--it;
						int k=it->second;
						ans=min(ans,f(Z[i],Z[k],r,v_abs));
					}
				}
			}

			if(Z[i].dir==1) S_u.insert(make_pair(Z[i].p.y,i));
			else            S_d.insert(make_pair(Z[i].p.y,i));
		}

		if(ans>INF/2) puts("SAFE");
		else          printf("%.9f\n",ans);
	}

	return 0;
}