하프 줄 길이

Lauren은 하프로 가능한 한 아름다운 음을 내려고 한다. 하프는 반지름이 $R$ 센티미터인 원이다. 음을 내려면 원둘레 위의 서로 다른 두 부착점을 잇도록 하프에 줄을 달아야 한다. 그다음 Lauren이 이 줄을 튕겨 음을 낸다.

원둘레에는 줄을 달 수 있는 부착점이 $N$개 있다. $i$번째 부착점은 원둘레의 가장 오른쪽 점에서 시계 방향으로 $D_i$나노도 떨어져 있다. 1나노도는 $10^{-9}$도이다.

부착점마다 줄을 고정하는 기술이 다르다. $i$번째 부착점은 고정하는 데 $L_i$센티미터의 줄이 필요하다. 서로 다른 두 부착점 $i$, $j$ 사이에 건 줄의 길이는 정확히 $L_i + L_j + d(i, j)$센티미터이다. 여기서 $d(i, j)$는 두 점을 잇는 현의 길이, 즉 두 점 사이의 유클리드 거리이다.

Lauren은 줄이 길수록 음이 좋다고 생각한다. Lauren의 하프에서 쓸 수 있는 줄 중 가장 긴 $K$개의 길이는 얼마인가?

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 세 정수 $N$, $R$, $K$가 주어진다. 각각 부착점의 수, 하프의 반지름(센티미터), 구하려는 줄 길이의 개수이다. 이어서 $N$개의 줄에 정수 $D_i$와 $L_i$가 주어진다. 각각 $i$번째 부착점의 위치(시계 방향, 나노도 단위)와 그 부착점에 필요한 줄의 길이(센티미터)이다.

각 테스트 케이스마다 Case #x: y1 y2 ... yK 형식으로 한 줄을 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y_n$은 가능한 줄 $N \times (N-1) / 2$개의 길이를 내림차순으로 정렬했을 때의 $n$번째 값이다. 각 $y_n$은 정답과 절대 오차 또는 상대 오차가 $10^{-9}$ 이내이면 맞은 것으로 본다.

• $1 \le T \le 100$.
• $N = 150000$인 테스트 케이스는 최대 10개이다.
• $N \ne 150000$인 모든 테스트 케이스에서 $5 \le N \le 10^4$이다.
• $1 \le R \le 10^9$.
• $0 \le D_1$.
• 모든 $i$에 대해 $D_i < D_{i+1}$.
• $D_N < 360 \times 10^9$.

서로 다른 쌍의 점을 잇는 줄끼리 교차해도 된다. Lauren은 한 번에 음 하나만 내기 때문이다.