Problem: Milky Way

Milky Way

English text is not available in this practice contest.

The Milky Way Transportation Corporation is a travel agency that plans and manages interstellar travel tours. The Milky Way Transportation Corporation is planning a project called "Milky Way Crossing Orihime Hikoboshi Experience Tour". This tour departs from Vega in Lyra and travels around the stars to Altair in Aquila. You are an employee of the Milky Way Transportation Corporation and are responsible for choosing the route of the tour.

For simplicity, the Milky Way shall be on two-dimensional coordinates, and the stars shall be represented by pentagrams. The spacecraft used for the tour is equipped with a special engine and can move on the pentagram line segment without energy. On the other hand, when moving between pentagrams, energy proportional to the distance is required.

In recent years, sales of the Milky Way Transportation Corporation have been sluggish, and there is a pressing need to save various necessary expenses such as energy costs for spacecraft. Your job is to find a route that minimizes the sum of interstellar travel distances when moving from Vega to Altair, and write a program that outputs that sum.

Note that when moving from one pentagram to another that is contained within it, if the pentagrams are not in contact with each other, they are treated as interstellar movements.

Figure D-1 illustrates the third Sample Input. In the figure, the red line segment represents the part of the interstellar movement of the route that minimizes the total interstellar movement distance.

<image>

Figure D-1: Movement between stars

Input

The input consists of one or more datasets. One dataset has the following format:

> N M L
> x1 y1 a1 r1
> x2 y2 a2 r2
> ...
> xN yN aN rN
>

The first line of each test case consists of the integers N, M, L, where N is the number of stars (1 ≤ N ≤ 100), M is the Vega number (1 ≤ M ≤ N), and L is the Altair number (1 ≤ M ≤ N). Represents 1 ≤ L ≤ N). Information on each star is given in the following N lines. Each row consists of four integers, xi, yi, ai, and ri, where xi is the x-coordinate of the center of the i-th star (0 ≤ xi ≤ 1,000) and yi is the y-coordinate of the center of the i-th star (0 ≤ yi). ≤ 1,000), ai is the angle formed by the straight line connecting the center coordinates of the i-th star and the tip of the star with the y-axis (0 ≤ ai <72), and ri is from the center coordinates of the i-th star to the tip of the star. The length (1 ≤ ri ≤ 1,000). The end of the input is represented by a line containing three zeros.

The star on the left in Figure D-2 represents the star with x = 5, y = 10, a = 0, r = 5, and the star on the right is x = 15, y = 10, a = 30, r = 5. Represents the star of.

<image>

Figure D-2: Star example

Output

For each input, output the minimum total interstellar movement distance required to move from Vega to Altair on one line. The output must not have an error greater than 0.000001.

Sample Input


1 1 1
5 5 0 5
2 1 2
5 5 0 5
15 5 0 5
3 2 3
15 15 0 5
5 5 10 5
25 25 20 5
0 0 0


Output for Sample Input


0.00000000000000000000
0.48943483704846357796
9.79033725601359705593






Example

Input




Output

Solution (in JAVA):

Solution:

import java.util.*;
import java.io.*;

import static java.util.Arrays.*;
import static java.util.Collections.*;
import static java.lang.Math.*;

public class Main {

	int INF = 1 << 28;
	//long INF = 1L << 62;
	double EPS = 1e-10;

	void run() {
		Scanner sc = new Scanner(System.in);
		for (;;) {
			int n = sc.nextInt(), m = sc.nextInt(), l = sc.nextInt();
			if ((n|m|l) == 0) break;
			m--; l--;

			Star[] stars = new Star[n];
			for (int i=0;i<n;i++) stars[i] = new Star(sc.nextInt(), sc.nextInt(), sc.nextInt(), sc.nextInt());

			double[][] d = new double[n][n];
			for (int i=0;i<n;i++) for (int j=i+1;j<n;j++) {
//				debug("star", i, j);
				d[i][j] = d[j][i] = stars[i].dist(stars[j]);
			}

			for (int k=0;k<n;k++) for (int i=0;i<n;i++) for (int j=0;j<n;j++)
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

			System.out.println(d[m][l]);
		}
	}


	double distSS (P p1, P p2, P q1, P q2) {
		if (cross(p1, p2, q1, q2)) return 0.0;
		double min = INF;
		min = min(min, disSP(p1, p2, q1));
		min = min(min, disSP(p1, p2, q2));
		min = min(min, disSP(q1, q2, p1));
		min = min(min, disSP(q1, q2, p2));
		return min;
	}

	//テァツつケテ」ツ?ィテァツキツ堙・ツ按?」ツ?ョティツキツ敕ゥツ崢「
	double disSP(P p1, P p2, P q) {
		if( p2.sub(p1).dot(q.sub(p1)) < EPS ) return q.sub(p1).abs();
		if( p1.sub(p2).dot(q.sub(p2)) < EPS ) return q.sub(p2).abs();
		return disLP(p1, p2, q);
	}

	//テァツつケテ」ツ?ィテァツ崢エテァツキツ堙」ツ?ョティツキツ敕ゥツ崢「
	double disLP(P p1, P p2, P q) {
		return Math.abs(p2.sub(p1).det(q.sub(p1))) / p2.sub(p1).abs();
	}

	//テァツキツ堙・ツ按?、ツコツ、テ・ツキツョテ・ツ按、テ・ツョツ?
	boolean cross(P p1, P p2, P q1, P q2) {
		return ccw(p1, p2, q1) * ccw(p1, p2, q2) <= 0 &&
			ccw(q1, q2, p1) * ccw(q1, q2, p2) <= 0;
	}

	//テヲツ卍づィツィツ暗・ツ崢榲」ツつ甘」ツ?ェテ」ツ?ョテ」ツ?凝ッツシツ偲・ツ渉催ヲツ卍づィツィツ暗・ツ崢榲」ツつ甘」ツ?ェテ」ツ?ョテ」ツ?凝ッツシツ古ァツ崢エテァツキツ堙ァツ環カテ」ツ?ェテ」ツ?ョテ」ツ?凝ッツシツ古」ツ?ィテ」ツ?ォテ」ツ?凝」ツ?湘、ツスツ催ァツスツョテゥツ鳴「テ、ツソツづ」ツつ津」ツ?ソテ」ツつ?
	int ccw (P a, P b, P c) {
		P s = b.sub(a);
		P t = c.sub(a);
		if( s.det(t) > EPS ) return 1;
		if( s.det(t) < -EPS ) return -1;
		if( s.dot(t) < -EPS ) return 2;
		if( s.dot(s) + EPS < t.dot(t) ) return -2;
		return 0;
	}

	class Star {
		P[] p;
		Star(int px, int py, int sh, int r) {
			p = new P[5];
			for (int i=0;i<5;i++) {
				p[i] = new P(1.0 * px - sin(1.0 * (i * 72 + sh) / 180.0 * PI) * r,
							 1.0 * py + cos(1.0 * (i * 72 + sh) / 180.0 * PI) * r);
			}
		}

		double dist(Star s) {
			double min = INF;
			for (int i=0;i<5;i++) for (int j=0;j<5;j++ ) {
				min = min(min, distSS(p[i], p[(i+2)%5], s.p[j], s.p[(j+2)%5]));
//				debug(i, j, min);
			}
			return min;
		}
	}

	public class P {
		double EPS = 1e-10;
		double x, y;
		P(double x, double y) {
			this.x = x;
			this.y = y;
		}

		double add(double a, double b) {	//ティツェツ、テ・ツキツョテ」ツつ津ィツ?εヲツ?ョ
			if( Math.abs(a+b) < EPS * ( Math.abs(a) + Math.abs(b) ) ) return 0;
			return a + b;
		}

		P add(P p) {	//テ・ツ陳?
			return new P(x+p.x, y+p.y);
		}

		P sub(P p) {	//テ・ツキツョ
			return new P(x-p.x, y-p.y);
		}

		P mlt(double k) {
			return new P(x*k, y*k);
		}

		double dot(P p) {	//テ・ツ??ァツゥツ?
				return add(x*p.x, y*p.y);
		}

		double det(P p) {	//テ・ツ、ツ姪ァツゥツ?
			return add(x*p.y, -y*p.x);
		}

		//ティツキツ敕ゥツ崢「テァツウツサ
		double abs() {
			double ret = sqrt( add(x*x, y*y) );
			if ( Math.abs(ret) < EPS ) return 0;
			return ret;
		}

		double abs(P p) {
			double dx = add( x, -p.x );
			double dy = add( y, -p.y );
			double ret = sqrt( add(dx*dx, dy*dy) );
			if( Math.abs(ret) < EPS ) return 0;
			return ret;
		}
	}

	void debug(Object... os) {
		System.err.println(Arrays.deepToString(os));
	}

	public static void main(String[] args) {
		new Main().run();
	}
}