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.io.IOException;
import java.util.Scanner;
import java.util.Stack;

class Solve{
	final Scanner in = new Scanner(System.in);
	
	static final double INF = 1e9;
	boolean solve(){
		int n = in.nextInt();
		int m = in.nextInt()-1;
		int l = in.nextInt()-1;
		if(n == 0) return false;
		double[][] dist = new double[n][n];
		Star[] st = new Star[n];
		for(int i=0; i<n; i++){
			st[i] = new Star(in.nextInt(), in.nextInt(), in.nextInt(), in.nextInt());
		}
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				if(j==i) continue;
				dist[i][j] = INF;
			}
		}
		for(int i=0; i<n-1; i++){
			for(int j=i+1; j<n; j++){
				dist[i][j] = dist[j][i] = st[i].dist(st[j]);
			}
		}
		for(int k=0; k<n; k++)
			for(int i=0; i<n; i++)
				for(int j=0; j<n; j++)
					dist[i][j] = Math.min(dist[i][j], dist[i][k]+dist[k][j]);
		System.out.println(dist[m][l]);
		return true;
	}
//	
//	String dump(double[][] d, int n){
//		
//	}
	
}

class Star{
	Pos[] p;
	static final double EPS = 1e-10;
	static final double INF = 1e9;
	Star(int x, int y, int a, int r){
		p = new Pos[5];
		for(int i=0; i<5; i++){
			double px = x + Math.cos(Math.toRadians(a+90+144*i))*r;
			double py = y + Math.sin(Math.toRadians(a+90+144*i))*r;
			p[i] = new Pos(px, py);
		}
	}
	
	double dist(Star s){
		double res = INF;
		for(int i=0; i<5; i++){
			Pos p1 = p[i];
			Pos p2 = p[(i+1)%5];
			res = Math.min(res, s.dist(p1, p2));
			res = Math.min(res, dist(s.p[i], s.p[(i+1)%5]));
		}
		return res;
	}
	
	double dist(Pos p1, Pos p2){
		double res = INF;
		for(int i=0; i<5; i++){
			res = Math.min(res, vecdist(p1, p2, p[i]));
			if(cross(p1, p2, p[i], p[(i+1)%5])) return 0;
		}
		return res;
	}
	
	boolean cross(Pos a1, Pos a2, Pos b1, Pos b2){
		if(cross(a1.x - a2.x, a1.y-a2.y, b1.x-b2.x, b1.y-b2.y) == 0
				&& cross(a1.x-a2.x, a1.y-a2.y, a1.x-b2.x, a1.y-b2.y) == 0){
			if(Math.abs(a1.dist2(b1)+a2.dist2(b1) - a1.dist2(a1)) < EPS
					|| Math.abs(a1.dist2(b2)+a2.dist2(b2) - a1.dist2(a2)) < EPS){
				return true;
			}else return false;
		}
		return triarea(a1, a2, b1)*triarea(a1, a2, b2) <= 0
				&& triarea(b1, b2, a1)*triarea(b1, b2, a2) <= 0;
	}
	
	double vecdist(Pos a, Pos b, Pos c){
		if(dot(b.x - a.x, b.y-a.y, c.x - a.x, c.y-a.y) <= EPS)
			return Math.sqrt(a.dist2(c));
		if(dot(a.x-b.x, a.y-b.y, c.x-b.x, c.y-b.y) <= EPS){
			return Math.sqrt(b.dist2(c));
		}
		return Math.abs(triarea(a, b, c)/Math.sqrt(a.dist2(b)));
	}
	
	double dot (double x, double y, double x1, double y1){
		return x*x1 + y*y1;
	}
	
	double triarea(Pos a, Pos b, Pos c){
		double dx1 = b.x - a.x;
		double dy1 = b.y - a.y;
		double dx2 = c.x - a.x;
		double dy2 = c.y - a.y;
		return dx1*dy2 - dx2*dy1;
	}
	
	double cross(double x1, double y1, double x2, double y2){
		return x1*y2 - x2*y1;
	}
}

class Pos{
	double x, y;
	Pos(double x, double y){
		this.x = x;
		this.y = y;
	}
	
	double dist2(Pos p){
		return (x-p.x)*(x-p.x)+(y-p.y)*(y-p.y);
	}
}

public class Main{
	public static void main(String[] args) throws IOException{
		Solve solve = new Solve();
		while(solve.solve());
	}
}