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.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true) {
			int n = sc.nextInt();
			int m = sc.nextInt();
			int l = sc.nextInt();
			if (n == 0) {
				break;
			}
			Vector2[][] p = new Vector2[n*5][2];
			for(int i=0;i<n;i++) {
				int x = sc.nextInt();
				int y = sc.nextInt();
				int a = sc.nextInt();
				int r = sc.nextInt();
				Vector2[] q = new Vector2[5];
				for(int j=0;j<5;j++) {
					double rad = Math.toRadians(90 + a + j * 72);
					q[j] = new Vector2(x + Math.cos(rad) * r, y + Math.sin(rad) * r);
//					System.out.println(q[j]);
				}
				for(int j=0;j<5;j++) {
					p[i*5+j][0] = q[j];
					p[i*5+j][1] = q[(j+2)%5];
				}
			}
			Graph g = new Graph(n*5);
			for(int i=0;i<n*5;i++) {
				for(int j=i+1;j<n*5;j++) {
					g.addBidirectionalEdge(i, j, Vector2.distLineToLine(p[i][0], p[i][1], p[j][0], p[j][1]));
				}
			}
			double dist = g.minDistDijkstra((m-1)*5)[(l-1)*5];
			System.out.println(String.format("%.8f", dist));
		}
	}

}
class Vector2 {
	public double x;
	public double y;
	public Vector2(double x,double y) {
		this.x = x;
		this.y = y;
	}
	public double dot(Vector2 v) {
		return this.x*v.x+this.y*v.y;
	}
	public double cross(Vector2 v) {
		return this.x*v.y-this.y*v.x;
	}
	public double norm() {
		return Math.sqrt(this.x*this.x+this.y*this.y);
	}
	public Vector2 normalize() {
		return divide(norm());
	}
	public Vector2 add(Vector2 v) {
		return new Vector2(x+v.x,y+v.y);
	}
	public Vector2 subtract(Vector2 v) {
		return new Vector2(x-v.x,y-v.y);
	}
	public Vector2 multiply(double k) {
		return new Vector2(x*k,y*k);
	}
	public Vector2 divide(double k) {
		return new Vector2(x/k,y/k);
	}
	public double dist(Vector2 p1) {
		return p1.subtract(this).norm();
	}
	public static double distLineToLine(Vector2 p0,Vector2 p1,Vector2 p2,Vector2 p3) {
		if (intersects(p0, p1, p2, p3)) {
			return 0;
		}
		double dist = Double.POSITIVE_INFINITY;
		dist = Math.min(dist, distLineToPoint(p0, p1, p2));
		dist = Math.min(dist, distLineToPoint(p0, p1, p3));
		dist = Math.min(dist, distLineToPoint(p2, p3, p0));
		dist = Math.min(dist, distLineToPoint(p2, p3, p1));
		return dist;
	}
	public static boolean intersects(Vector2 p0,Vector2 p1,Vector2 p2,Vector2 p3) {
		Vector2 v1 = p1.subtract(p0);
		Vector2 v2 = p3.subtract(p2);
		Vector2 v = p2.subtract(p0);
		Vector2 v_ = p2.subtract(p1);
		double a = v1.cross(v2);
		if(a==0) {
			return v.cross(v_) == 0 && (v.dot(v_) <= 0 || p0.subtract(p2).dot(p0.subtract(p3)) <= 0);
		}else{
			double a1 = -v1.cross(v);
			double a2 = -v2.cross(v);
			if (a>0) {
				return (0<=a1&&a1<=a&&0<=a2&&a2<=a);
			}else{
				return (a<=a1&&a1<=0&&a<=a2&&a2<=0);
			}
		}
	}
	public static double distLineToPoint(Vector2 r1,Vector2 r2,Vector2 p) {
		Vector2 r12 = r2.subtract(r1);
		if (p.subtract(r1).dot(r12) * p.subtract(r2).dot(r12) >= 0) {
			return Math.min(p.dist(r1), p.dist(r2));
		}else{
			return Math.abs(r2.subtract(r1).normalize().cross(p.subtract(r1)));
		}
	}
	public String toString() {
		return "(" + this.x + "," + this.y + ")";
	}
}
class Graph {
	public static final int INF = 1<<29;
	int n;
	ArrayList<Edge>[] graph;

	@SuppressWarnings("unchecked")
	public Graph(int n) {
		this.n = n;
		this.graph = new ArrayList[n];
		for(int i=0;i<n;i++) {
			graph[i] = new ArrayList<Edge>();
		}
	}
	
	public void addBidirectionalEdge(int from,int to,double cost) {
//		System.out.println(from + "," + to + "," + cost);
		addEdge(from,to,cost);
		addEdge(to,from,cost);
	}
	public void addEdge(int from,int to,double cost) {
		graph[from].add(new Edge(to, cost));
	}

	//dijkstra O(ElogV)
	public double[] minDistDijkstra(int s) {
		double[] dist = new double[n];
		Arrays.fill(dist, INF);
		dist[s] = 0;
		PriorityQueue<Node> q = new PriorityQueue<Node>();
		q.offer(new Node(0, s));
		while(!q.isEmpty()) {
			Node node = q.poll();
			int v = node.id;
			if (dist[v] < node.dist) {
				continue;
			}
			for(Edge e:graph[v]) {
				if (dist[e.to] > dist[v] + e.cost) {
					dist[e.to] = dist[v] + e.cost;
					q.add(new Node(dist[e.to], e.to));
				}
			}
		}
		return dist;
	}

	class Edge {
		int to;
		double cost;
		public Edge(int to,double cost) {
			this.to = to;
			this.cost = cost;
		}
	}
	class Node implements Comparable<Node>{
		double dist;
		int id;
		public Node(double dist,int i) {
			this.dist = dist;
			this.id = i;
		}
		public int compareTo(Node o) {
			return (this.dist < o.dist) ? -1 : ((this.dist == o.dist) ? 0 : 1);
		}
	}
}