Musical Cords

Lauren is trying to play the most beautiful notes possible using a harp. The harp is a circle with a radius of $R$ centimeters. To play a note, a cord must be attached to the harp so that it connects two different attachment points on the perimeter of the circle. Lauren then plucks this cord to play a note.

There are $N$ attachment points on the perimeter of the harp where a cord can be attached. The $i$-th attachment point is $D_i$ nanodegrees clockwise from the rightmost point of the perimeter, where a nanodegree is $10^{-9}$ degrees.

The attachment points do not all use the same technology. The $i$-th attachment point requires $L_i$ centimeters of cord for fixing. A cord fixed between two different attachment points $i$ and $j$ is exactly $L_i + L_j + d(i, j)$ centimeters long, where $d(i, j)$ is the length of the chord between points $i$ and $j$, that is, the Euclidean distance between the two points.

Lauren thinks notes sound better when they come from longer cords. What are the $K$ longest cords that can be used with Lauren's harp?

The first line contains the number of test cases $T$. Each test case starts with a line containing three integers $N$, $R$, and $K$: the number of attachment points, the radius of the harp in centimeters, and the number of cord lengths to report. The next $N$ lines each contain two integers $D_i$ and $L_i$, the position in nanodegrees clockwise from the rightmost point and the cord length in centimeters needed at the $i$-th attachment point.

For each test case, output one line in the form Case #x: y1 y2 ... yK, where $x$ is the test case number starting from 1, and $y_n$ is the $n$-th value in the sorted (non-increasing) list of all $N \times (N-1) / 2$ cord lengths. Each $y_n$ is correct if it is within an absolute or relative error of $10^{-9}$ of the correct answer.

• $1 \le T \le 100$.
• $N = 150000$ in at most 10 cases.
• $5 \le N \le 10^4$ in all cases where $N \ne 150000$.
• $1 \le R \le 10^9$.
• $0 \le D_1$.
• $D_i < D_{i+1}$ for all $i$.
• $D_N < 360 \times 10^9$.

Cords between different pairs of points may cross each other, since Lauren plays only one note at a time.