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.awt.geom.Point2D;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		while (true) {
			int n = sc.nextInt();
			int m = sc.nextInt();
			int l = sc.nextInt();
			if ((n | m | l) == 0)
				break;
			double[][] dis = new double[n + 1][n + 1];
			Star[] stars = new Star[n + 1];
			for (int i = 1; i <= n; i++) {
				Arrays.fill(dis[i], Double.MAX_VALUE);
				dis[i][i] = 0;
			}
			for (int i = 1; i <= n; i++) {
				stars[i] = new Star(sc.nextDouble(), sc.nextDouble(),
						sc.nextDouble(), sc.nextDouble());
			}
			for (int i = 1; i <= n; i++) {
				for (int j = i + 1; j <= n; j++) {
					dis[i][j] = dis[j][i] = stars[i].minDistance(stars[j]);
				}
			}
			System.out.println();
			for (int k = 1; k <= n; k++) {
				for (int i = 1; i <= n; i++) {
					for (int j = 1; j <= n; j++) {
						dis[i][j] = Math.min(dis[i][j], dis[i][k] + dis[k][j]);
					}
				}
			}
			System.out.printf("%.10f\n", dis[m][l]);
		}
	}
}

class Star {
	Line[] ls = new Line[5];

	Star(double sx, double sy, double a, double r) {
		double x = sx - r * Math.sin(Math.PI * a / 180);
		double y = sy + r * Math.cos(Math.PI * a / 180);
		Point2D.Double[] ps = new Point2D.Double[5];
		ps[0] = new Point2D.Double(x, y);
		double cos = Math.cos(Math.PI * 72 / 180);
		double sin = Math.sin(Math.PI * 72 / 180);
		for (int i = 1; i < 5; i++) {
			double xd = (cos * (x - sx) - sin * (y - sy)) + sx;
			double yd = (sin * (x - sx) + cos * (y - sy)) + sy;
			ps[i] = new Point2D.Double(xd, yd);
			x = xd;
			y = yd;
		}
		ls[0] = new Line(ps[0], ps[2]);
		ls[1] = new Line(ps[2], ps[4]);
		ls[2] = new Line(ps[4], ps[1]);
		ls[3] = new Line(ps[1], ps[3]);
		ls[4] = new Line(ps[3], ps[0]);
	}

	public double minDistance(Star star2) {
		Star star1 = this;
		double min = Double.MAX_VALUE;
		for (int i = 0; i < 5; i++) {
			for (int j = 0; j < 5; j++) {
				min = Math.min(min, star1.ls[i].minDistance(star2.ls[j]));
			}
		}
		return min;
	}

	public String toString() {
		return this.ls[0] + " " + this.ls[1] + " " + this.ls[2] + " "
				+ this.ls[3] + " " + this.ls[4];
	}
}

class Line {
	public Point2D.Double p1;
	public Point2D.Double p2;

	Line(Point2D.Double p1, Point2D.Double p2) {
		this.p1 = p1;
		this.p2 = p2;
	}

	public double length() {
		return Math.sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y)
				* (p1.y - p2.y));
	}

	public double ip(Line l) {
		Point2D.Double q1 = l.p1;
		Point2D.Double q2 = l.p2;
		return (p2.x - p1.x) * (q2.x - q1.x) + (p2.y - p1.y) * (q2.y - q1.y);
	}

	public double ep(Line l) {
		Point2D.Double q1 = l.p1;
		Point2D.Double q2 = l.p2;
		return (p2.x - p1.x) * (q2.y - q1.y) - (p2.y - p1.y) * (q2.x - q1.x);
	}

	public double disToPoint(Point2D.Double q1) {
		Line p1q1 = new Line(p1, q1);
		double ip1 = p1q1.ip(this);
		double ip2 = this.ip(this);
		if (ip1 <= 0)
			return p1q1.length();
		else if (0 < ip1 && ip1 < ip2) {
			double d2 = ip1 / this.length();
			double size = p1q1.length();
			return Math.sqrt(size * size - d2 * d2);
		} else {
			Line p2q1 = new Line(p2, q1);
			return p2q1.length();
		}
	}

	public boolean isCross(Line q1q2) {
		Point2D.Double q1 = q1q2.p1;
		Point2D.Double q2 = q1q2.p2;
		Line p1q1 = new Line(p1, q1);
		Line p1q2 = new Line(p1, q2);
		Line q1p1 = new Line(q1, p1);
		Line q1p2 = new Line(q1, p2);
		if (this.ep(p1q1) * this.ep(p1q2) < 0
				&& q1q2.ep(q1p1) * q1q2.ep(q1p2) < 0)
			return true;
		else
			return false;
	}

	public double minDistance(Line q1q2) {
		if (this.isCross(q1q2))
			return 0;
		double ans = Double.MAX_VALUE;
		Point2D.Double q1 = q1q2.p1;
		Point2D.Double q2 = q1q2.p2;
		ans = Math.min(ans, this.disToPoint(q1));
		ans = Math.min(ans, this.disToPoint(q2));
		ans = Math.min(ans, q1q2.disToPoint(p1));
		ans = Math.min(ans, q1q2.disToPoint(p2));
		return ans;
	}

	public String toString() {
		return p1 + "=>" + p2;
	}
}