음악의 줄

Lauren은 하프를 사용해 가능한 한 가장 아름다운 음을 연주하려 한다. 이 하프는 반지름이 R센티미터인 원이다. 음을 연주하려면 원의 둘레에 있는 서로 다른 두 부착 지점을 연결하는 방식으로 줄을 하프에 부착해야 한다. 그런 다음 Lauren은 이 줄을 뜯어 음을 연주한다.

원형 하프의 둘레에는 줄을 부착할 수 있는 N개의 부착 지점이 있다. 이들 중 i번째 부착 지점은 둘레의 가장 오른쪽 지점에서 시작해 원형 하프의 둘레를 시계 방향으로 $D_{i}$나노도(나노도는 10^{-9}도이다)만큼 이동한 위치에 있다.

모든 부착 지점이 줄을 제대로 고정하는 데 같은 기술을 사용하는 것은 아니다. i번째 부착 지점에 부착하려면 줄 $L_{i}$센티미터를 사용해야 한다. 서로 다른 두 부착 지점 i와 j 사이에 고정되는 줄의 길이는 정확히 $L_{i}$ + $L_{j}$ + distance(i, j)센티미터여야 한다. distance(i, j)는 i번째 부착 지점과 j번째 부착 지점을 연결하는 기하학적 현의 길이, 즉 두 지점 사이의 유클리드 거리를 뜻한다.

Lauren은 더 긴 줄에서 나오는 음이 더 아름답다고 생각한다. Lauren의 하프에 사용할 수 있는 줄 중 가장 긴 K개의 길이는 무엇인가?

제한

시간 제한: 테스트 세트당 120초. 메모리 제한: 1GB. 1 ≤ T ≤ 100. 최대 10개의 경우에서 N = 150000. N ≠ 150000인 모든 경우에 5 ≤ N ≤ $10^{4}$. 1 ≤ R ≤ $10^{9}$. 0 ≤ $D_{1}$. 모든 i에 대해 $D_{i}$ < $D_{i+1}$. $D_{N}$ < 360 × $10^{9}$.

테스트 세트 1 (Visible Verdict)

각 i에 대해 $L_{i}$은 1 이상 $10^{9}$ 이하에서 독립적으로 균등하게 무작위로 선택된다. K = 1.

테스트 세트 2 (Hidden Verdict)

모든 i에 대해 1 ≤ $L_{i}$ ≤ $10^{9}$. (각 $L_{i}$이 생성되는 방식에 대해서는 어떠한 보장도 없다.) K = 10.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 세 정수 N, R, K가 주어진다. 이는 각각 부착 지점의 수, 원형 하프의 반지름을 센티미터 단위로 나타낸 값, Lauren이 알고 싶어 하는 줄 길이의 개수이다.

다음 N개의 줄에는 부착 지점이 설명된다. 이들 중 i번째 줄에는 두 정수 $D_{i}$와 $L_{i}$가 주어지며, 각각 i번째 부착 지점의 위치(하프의 가장 오른쪽 지점에서 시계 방향으로 잰 나노도의 수)와 부착에 필요한 줄의 길이를 센티미터 단위로 나타낸다.

각 테스트 케이스마다 Case #x: y_{1} y_{2} ... y_{K}을 포함하는 한 줄을 출력한다. 여기서 x은 (1부터 시작하는) 테스트 케이스 번호이고, y_{n}은 Lauren의 하프에 사용할 수 있는 모든 N×(N-1)/2개 줄의 길이를 내림차순으로 정렬한 목록에서 n번째 값이다.

각 y_{n}은 정답과의 절대 오차 또는 상대 오차가 10^{-9} 이내이면 정답으로 간주된다. 이것이 의미하는 바와 허용되는 실수 형식에 대한 설명은 FAQ을 참조하라.

위의 케이스들은 테스트 세트 1의 제한을 만족한다. 이 제한을 만족하지 않는 또 다른 예제 케이스가 이 절의 끝에 제시되어 있다.

참고: 테스트 세트 1의 이 예제 케이스들에 사용된 $L_{i}$ 값은 이해하기 쉽도록 선택된 것이며 무작위로 생성되지 않았다. 제출한 풀이는 이 예제 케이스들에 대해서도 실행되며 반드시 통과해야 한다.

예제 케이스 #1에서는 모든 부착 지점의 값이 같으므로, 가장 긴 현으로 연결된 쌍을 선택해야 한다. 이 경우에는 길이가 4센티미터인 원의 수평 지름이다. 따라서 필요한 총길이는 4 + 3 + 3 = 10센티미터이다.

예제 케이스 #2에서는 네 번째와 다섯 번째 지점이 세 번째 지점에 매우 가깝지만 L 값은 훨씬 작다. 이들을 사실상 제외하고 다음과 같이 첫 세 지점 사이에서 가능한 연결에 집중할 수 있다.

• 첫 번째 지점과 두 번째 지점: 길이 10√2 + 8 + 7: ≈29.142136.

• 첫 번째 지점과 세 번째 지점: 길이 ≈19.923894 + 8 + 9: ≈36.923894.

• 두 번째 지점과 세 번째 지점: 길이 ≈12.855726 + 7 + 9: ≈28.855726.

첫 번째 지점과 세 번째 지점을 사용하면 총길이가 가장 길다.

다음 추가 케이스는 테스트 세트 1에는 나올 수 없지만 테스트 세트 2에는 나올 수 있다.

올바른 출력은 Case #1: 12.2175228580 12.0000000000 11.7653668647 11.5176380902 11.2610523844 3.0000000000 2.7653668647 2.7653668647 2.5176380902 2.5176380902이다.

가능한 지점 쌍 세 개가 9번째로 긴 줄을 만드는 공동 순위를 이룬다는 점에 유의하라. 또한 Lauren은 한 번에 하나의 음만 연주하므로 서로 다른 지점 쌍을 연결하는 선들이 교차해도 괜찮다.