Lauren 正在尝试用竖琴演奏出最动听的音符。竖琴是一个半径为 $R$ 厘米的圆。要演奏一个音符，必须将一根弦连接到圆周上的两个不同的连接点上。然后，Lauren 拨动这根弦来演奏音符。
圆形的竖琴圆周上有 $N$ 个连接点，弦可以连接在这些点上。第 $i$ 个连接点位于圆周上，从圆周最右侧的点开始顺时针测量，位置为 $D_i$ 纳度（$1$ 纳度为 $10^{-9}$ 度）。
并非所有的连接点都使用相同的技术来固定弦。第 $i$ 个连接点需要 $L_i$ 厘米的弦来固定。连接两个不同连接点 $i$ 和 $j$ 的弦需要恰好 $L_i + L_j + \text{distance}(i, j)$ 厘米长。这里 $\text{distance}(i, j)$ 指的是连接第 $i$ 个和第 $j$ 个连接点的几何弦长，即两点之间的欧几里得距离。
Lauren 认为弦越长，音符听起来就越好。请问 Lauren 的竖琴可以使用哪 $K$ 根最长的弦？
输入格式
输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含三个整数：$N$、$R$ 和 $K$，分别表示连接点的数量、圆形竖琴的半径（单位：厘米）以及 Lauren 感兴趣的弦的长度数量。
接下来的 $N$ 行描述了连接点。第 $i$ 行包含两个整数 $D_i$ 和 $L_i$，分别描述了第 $i$ 个连接点的位置（从竖琴最右侧点开始顺时针测量的纳度数）和固定该点所需的弦长（单位：厘米）。
输出格式
对于每个测试用例，输出一行 Case #x: y1 y2 ... yK，其中 $x$ 是测试用例编号（从 $1$ 开始），$y_n$ 是 Lauren 的竖琴上所有 $N \times (N-1)/2$ 根可用弦的长度列表中的第 $n$ 个值，按非递增顺序排列。
如果每个 $y_n$ 与正确答案的绝对误差或相对误差在 $10^{-9}$ 以内，则被视为正确。有关该定义的解释以及我们接受的实数格式，请参阅 FAQ。
数据范围
时间限制：每个测试集 120 秒。 内存限制：1GB。 $1 \le T \le 100$。 $N = 150000$ 的情况最多有 10 个。 在所有 $N \neq 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$。
测试集 1（可见判定）
对于每个 $i$，$L_i$ 在 $1$ 到 $10^9$ 之间独立均匀随机选择。 $K = 1$。
测试集 2（隐藏判定）
对于所有 $i$，$1 \le L_i \le 10^9$。 （不保证 $L_i$ 的生成方式。） $K = 10$。
样例
输入 1
2 5 2 1 0 3 1234567890 3 3154510113 3 180000000000 3 359999999999 3 5 10 1 90000000000 8 180000000000 7 260000000000 9 260000000001 1 260000000002 1
输出 1
Case #1: 10.0000000000 Case #2: 36.9238939618
说明
上述样例符合测试集 1 的限制。本节末尾提供了另一个不符合这些限制的样例。
注意：测试集 1 样例中的 $L_i$ 值是为了方便理解而选择的，并非随机生成。您的解决方案将针对这些样例进行运行，并且必须通过它们。
在样例 1 中，所有的连接点具有相同的值，因此我们应该选择由最长弦连接的一对点，在本例中是圆的水平直径，长度为 4 厘米。所以所需的总长度为 $4 + 3 + 3 = 10$ 厘米。
在样例 2 中，第四个和第五个点非常靠近第三个点，但 $L$ 值要小得多。我们可以有效地排除它们，并将重点放在前三个点之间的可能连接上，如下所示： 第一点和第二点：长度 $10\sqrt{2} + 8 + 7 \approx 29.142136$。 第一点和第三点：长度 $\approx 19.923894 + 8 + 9 \approx 36.923894$。 * 第二点和第三点：长度 $\approx 12.855726 + 7 + 9 \approx 28.855726$。
使用第一点和第三点能给我们带来最大的总长度。
以下额外样例不会出现在测试集 1 中，但可能出现在测试集 2 中：
1 6 1 10 0 10 15000000000 1 30000000000 1 45000000000 1 60000000000 1 75000000000 1
正确输出为 Case #1: 12.2175228580 12.0000000000 11.7653668647 11.5176380902 11.2610523844 3.0000000000 2.7653668647 2.7653668647 2.5176380902 2.5176380902。
请注意，有三对可能的点并列产生第 9 长的弦。此外，连接不同点对的线相交也是可以的，因为 Lauren 一次只会演奏一个音符。