최적의 우주 도로

서기 2180년, 인류는 지구를 떠나 우주에 정착하기 시작했다. 모든 도시가 하나의 표준 업무 시간을 공유할 수 있도록 수천 개의 우주 도시가 하나의 가상 평면 위에 건설되었고, 따라서 각 도시의 위치는 2차원 좌표평면 위의 한 점 $(x, y)$ 로 나타낼 수 있다.

도시들은 서로 멀리 떨어져 있어 도시 사이를 오가는 유일한 수단은 왕복 로켓뿐이다. 로켓 비용이 매우 비싸기 때문에, 우주 기관은 양방향으로 무한히 뻗을 수 있는 완벽한 직선 도로 하나(초우주 도로, SSW) 를 건설하기로 한다.

도시 $c_1$ 에서 도시 $c_2$ 로 이동할 때, 여행자는 먼저 $c_1$ 에서 SSW 위의 가장 가까운 지점까지 로켓으로 날아가고, SSW 를 따라 저렴하게 이동한 뒤, $c_2$ 에서 가장 가까운 SSW 위의 지점에서 다시 로켓을 타고 $c_2$ 로 간다. 직선 위에서 어떤 도시에 가장 가까운 지점은 그 도시에서 직선에 내린 수선의 발이므로, 한 도시의 로켓 이동 거리는 그 도시에서 SSW 까지의 수직 거리와 같다.

거리 $v$ 를 나는 로켓의 비용은 $v^2$ 이며, SSW 를 따라 이동하는 비용은 상대적으로 무시할 수 있어 계산에 넣지 않는다. 모든 보통 도시는 한 해 동안 같은 수의 로켓 편(도착 + 출발)을 보낸다. 연간 총 로켓 비용이 최소가 되도록 SSW 를 배치하고, 그때의 최소 로켓 편당 평균 비용 을 구하여라.

모든 보통 도시의 로켓 편 수가 같으므로, 로켓 편당 평균 비용은 각 도시에서 SSW 까지의 수직 거리 제곱의 평균과 정확히 같고, 이 평균을 최소로 만드는 직선을 자유롭게 고를 수 있다.

때때로 정확히 한 도시가 모든 활동의 중심인 슈퍼 도시 로 지정된다. 슈퍼 도시는 보통 도시보다 $M$ 배 많은 로켓 편(도착 + 출발)을 가지며, 나머지 도시는 모두 보통 도시로 남는다. 이 경우 각 도시의 수직 거리 제곱에 그 도시의 로켓 편 수를 가중치로 곱하며, 최소 가중 평균 비용, 즉 모든 직선에 대한 $\dfrac{\sum_i w_i, d_i^2}{\sum_i w_i}$ 의 최솟값을 구한다. 여기서 $d_i$ 는 도시 $i$ 에서 직선까지의 수직 거리이고, 슈퍼 도시는 $w_i = M$, 나머지 보통 도시는 $w_i = 1$ 이다.

가정: 도시는 점으로 간주한다. SSW 는 두께가 없는 직선이며, 비용을 줄일 수 있다면 어느 방향으로든 길이를 무한히 늘일 수 있다. 모든 로켓은 직선으로 난다.

입력은 $50$ 개 미만의 테스트 케이스로 이루어진다.

각 테스트 케이스는 두 정수 $N$ 과 $Q$ ($0 < N \le 10000$, $0 < Q \le 100$) 로 시작한다. $N$ 은 우주 도시의 수, $Q$ 는 질의의 수이다. 이어지는 $N$ 개의 줄에는 각각 두 실수 $x_i$ 와 $y_i$ ($0.0 \le x_i, y_i \le 1000.0$), 즉 $i$ 번째 도시의 좌표가 주어진다. 도시는 입력에 나타나는 순서대로 $0$ 부터 $N-1$ 까지 번호가 매겨진다. 이어지는 $Q$ 개의 줄에는 각각 두 정수 $S$ 와 $M$ ($0 \le S \le N-1$, $1 < M \le 10000$) 이 주어진다. 도시 $S$ 가 슈퍼 도시이며, 그 로켓 편 총수는 보통 도시의 $M$ 배이다.

두 개의 $0$ 으로 이루어진 줄이 나오면 입력이 끝나며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 $Q + 2$ 개의 줄을 출력한다.

• 첫 번째 줄은 Case k: 로, $k$ 는 $1$ 부터 시작하는 테스트 케이스 번호이다.
• 두 번째 줄은 모든 도시가 보통 도시일 때의 최소 로켓 편당 평균 비용이다.
• 이어지는 $Q$ 개의 줄은 주어진 순서대로 각 질의에 대응하며, i: value 형식이다. $i$ 는 $1$ 부터 시작하는 질의 번호이고, value 는 해당 질의의 도시 $S$ 가 슈퍼 도시이고 나머지 도시가 모두 보통 도시일 때의 최소 로켓 편당 평균 비용이다.

모든 비용은 소수점 아래 정확히 다섯 자리까지 출력해야 한다.