최단 비행 경로

통계상으로 상업 비행기는 꽤 안전하다. 초창기의 비행기는 기술적인 측면에서 현재의 비행기에 비해 엔진 신뢰성이 낮아서 항로상에서 인근 공항으로 부터 60분 이상 떨어져서 비행하는 것을 금지했기 때문이다. 지금도 다양한 규칙들이 존재하지만 핵심 내용은 이 "60분의 규칙"과 비슷하다. 비행기가 가장 가까운 공항에서 허용된 최대 거리 이상 멀어지면 안 된다는 것이다. 이러한 제약 사항 때문에 비행기가 곧바로 공항까지 갈 수 없는 경우도 종종 있다.

우리는 최대 허용 거리를 준수하면서 주어진 두 공항 사이를 이동하는 최단 경로를 계산해야 한다. 아래 보이는 그림은 첫 번째 테스트 케이스에 대한 자료를 나타낸다. 비행기의 항로는 반드시 주어진 세개의 원 어딘가에 존재해야 하며 2번에서 3번 공항으로 이동하려면 반드시 1번 공항의 원을 거쳐야 한다. 비행기가 공항 1에 도착할 필요는 없다.

비행기의 연료는 제한되어있기 때문에 최단 경로보다 긴 경로로 이동할 경우 연료 부족으로 도중에 착륙해야 할 수도 있다. 따라서 연료 용량에 따라 공항 1까지 가야 하는 경우가 생길 수도 있다. 공항 1까지 가는데 필요한 연료도 부족한 경우엔 도착지 까지 갈 수 없는 경우이다.

위와 같은 가정을 아래처럼 단순화 할 수 있다.

1. 지구의 표면은 반경 6370 km 이다.
2. 시간과 연료 소비량은 모두 이동거리에 비례한다. 즉, 우리는 이동거리에만 관심이  있다.
3. 고도에 따른 거리 차이는 무시한다. 즉, 비행기가 표현에 따라 비행한다고 가정한다.
4. 비행기는 필요에 따라 중간 지점의 공항에서 연료를 공급받을 수 있다. 한번 공급받을때 연료를 모두 채운다.

각 테스트 케이스의 첫 번째 줄에 정수 N 과 R 이 주어진다 (2 ≤ N ≤ 25, 1 ≤ R ≤ 10 000). N은 공항의 수 이고 R은 최대 허용 거리(km)이다. 다음 N개의 줄에는 공항의 경도와 위도를 나타내는 정수 Φ, θ가 주어진다(0 ≤ Φ < 360, -90 ≤ θ ≤ 90). 공항의 번호는 각각 1부터 입력받은 순서로주어지며 두 공항이 같은 위치에 있는 경우는 없다.

이어지는 줄에는 정수 Q가 주어진다 (1 ≤ Q ≤ 100). 각각의 Q개의 줄에는 출발 공항 번호, 도착 공항 번호, 연료의 용량(최대 연료 이동할 수 있는 거리)을 나타내는 세개의 정수 s, t, c가 주어진다 (1 ≤ s,  t ≤ N, s ≠ t,  1 ≤ c ≤ 50 000).

각각의 테스트 케이스 첫 번째 줄에 예제와 같이 테스트 케이스의 번호를 출력한다. 뒤이어 한줄씩 s, t, c를 만족하는 최단 비행 경로를 소숫점 셋째 자리 까지 출력한다. 가능한 경로가 존재하지 않다면 "impossible" 을 출력한다.