최단 비행 경로

통계적으로 상업용 비행기는 상당히 안전하다. 초창기 비행기는 엔진 신뢰성이 낮아, 항로 위에서 가장 가까운 공항으로부터 60분 이상 떨어져 비행하는 것이 금지되었기 때문이다. 오늘날에도 여러 규칙이 있지만 그 핵심은 이 "60분 규칙"과 비슷하다. 즉, 비행기는 언제나 가장 가까운 공항으로부터 허용된 최대 거리보다 더 멀리 떨어질 수 없다. 이 제약 때문에 목적지 공항까지 곧바로 갈 수 없는 경우가 생긴다.

우리는 이 최대 허용 거리를 지키면서 두 공항 사이를 이동하는 최단 경로의 길이를 구해야 한다. 각 공항을 중심으로 반지름이 최대 허용 거리인 원(구면 위의 영역)을 그리면, 비행기의 항로는 반드시 이 원들의 합집합 안에만 존재해야 한다. 예를 들어 어떤 배치에서는 2번 공항에서 3번 공항으로 가려면 반드시 1번 공항의 원을 거쳐야 할 수 있다. 다만 비행기가 실제로 1번 공항에 착륙(도달)할 필요는 없다.

비행기의 연료는 제한되어 있다. 연료를 가득 채워 한 번에 이동할 수 있는 최대 거리를 연료 용량이라고 하자. 최단 경로가 이 용량보다 길면, 도중에 공항에 착륙해 연료를 보충해야 한다. 목적지로 가는 도중 어떤 공항에도 닿지 못해 연료가 바닥나면, 그 경로로는 목적지에 도달할 수 없다.

문제를 다음과 같이 단순화한다.

1. 지구 표면은 반지름 6370 km인 구이다.
2. 이동에 걸리는 시간과 연료 소비량은 모두 이동 거리에 비례한다. 따라서 우리는 이동 거리에만 관심이 있다.
3. 고도에 따른 거리 차이는 무시한다. 즉, 비행기는 구 표면을 따라 비행한다고 가정한다.
4. 비행기는 필요에 따라 중간 공항에서 연료를 보충할 수 있으며, 한 번 보충할 때 연료 탱크를 가득 채운다.
5. 출발 공항에서는 연료 탱크를 가득 채운 상태로 출발한다.

각 테스트 케이스의 첫 번째 줄에 두 정수 $N$과 $R$이 주어진다 ($2 \le N \le 25$, $1 \le R \le 10000$). $N$은 공항의 수, $R$은 최대 허용 거리(km)이다.

이어지는 $N$개의 줄에는 각 공항의 경도와 위도를 나타내는 두 정수 $\Phi$, $\theta$가 주어진다 ($0 \le \Phi < 360$, $-90 \le \theta \le 90$). 공항의 번호는 입력된 순서대로 1번부터 $N$번까지이며, 서로 다른 두 공항이 같은 위치에 있는 경우는 없다.

그다음 줄에는 정수 $Q$가 주어진다 ($1 \le Q \le 100$). 이어지는 $Q$개의 줄에는 각각 세 정수 $s$, $t$, $c$가 주어진다 ($1 \le s, t \le N$, $s \ne t$, $1 \le c \le 50000$). $s$는 출발 공항 번호, $t$는 도착 공항 번호, $c$는 연료 용량(연료를 가득 채워 한 번에 이동할 수 있는 최대 거리, km)이다.

입력은 파일 끝까지 여러 개의 테스트 케이스가 이어진다.

각 테스트 케이스마다, 먼저 Case x: 형식으로 테스트 케이스 번호를 출력한다(예제 형식과 동일하며 $x$는 1부터 시작한다).

그다음 각 질의에 대해 한 줄씩, 조건 $s$, $t$, $c$를 만족하는 최단 비행 경로의 길이를 소수점 아래 셋째 자리까지 출력한다. 가능한 경로가 존재하지 않으면 impossible을 출력한다.