题目描述

Lauren 正尝试用竖琴演奏最美妙的音符。竖琴是一个半径为 $\mathbf{R}$ 厘米的圆形乐器。要演奏一个音符，必须在圆周上两个不同的固定点之间连接一根琴弦，并通过拨动琴弦发声。

圆周上共有 $\mathbf{N}$ 个固定点可用于连接琴弦。第 $i$ 个固定点的位置为从圆周最右侧点顺时针方向 $\mathbf{D}_i$ 纳度（1 纳度 = $10^{-9}$ 度）处。

不同固定点使用的固定技术不同。第 $i$ 个固定点需要消耗 $\mathbf{L}_i$ 厘米的琴弦用于固定。连接两个不同固定点 $i$ 和 $j$ 的琴弦总长度必须恰好为 $\mathbf{L}_i + \mathbf{L}_j + \text{distance}(i, j)$ 厘米。其中 $\text{distance}(i, j)$ 表示第 $i$ 个和第 $j$ 个固定点之间的几何弦长（即两点间的欧几里得距离）。

Lauren 认为琴弦越长，音符听起来越美妙。请问 Lauren 的竖琴可以使用的琴弦中，最长的 $\mathbf{K}$ 个长度分别是多少？

输入格式

第一行输入测试用例数 $\mathbf{T}$。每个测试用例包含：
第一行三个整数 $\mathbf{N}$、$\mathbf{R}$ 和 $\mathbf{K}$：固定点数量、竖琴半径（厘米）和 Lauren 需要查询的琴弦长度数量。
接下来 $\mathbf{N}$ 行描述固定点，每行两个整数 $\mathbf{D}_i$ 和 $\mathbf{L}_i$，分别表示第 $i$ 个固定点的位置（纳度）和固定所需琴弦长度（厘米）。

输出格式

对每个测试用例，输出一行 Case #x: y1 y2 ... yK，其中 $x$ 为测试用例编号（从 1 开始），$y_n$ 为所有 $\mathbf{N} \times (\mathbf{N}-1)/2$ 根可能琴弦的长度按非递增排序后的第 $n$ 个值。

每个 $y_n$ 允许存在绝对或相对误差不超过 $10^{-9}$。

输入输出样例 #1

输入 #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

输入输出样例 #2

输入 #2

1
6 1 10
0 10
15000000000 1
30000000000 1
45000000000 1
60000000000 1
75000000000 1

输出 #2

Case #1: 12.2175228580 12.0000000000 11.7653668647 11.5176380902 11.2610523844 3.0000000000 2.7653668647 2.7653668647 2.5176380902 2.5176380902

说明/提示

样例解释

样例测试集 1 符合测试集 1 的限制条件。其他不符合该限制的样例可能出现在测试集 2 中。

注意：测试集 1 的样例中 $\mathbf{L}_i$ 值是为便于理解而设定的非随机值。您的解法必须通过这些样例。

在样例 #1 中，所有固定点的 $\mathbf{L}_i$ 值相同，因此应选择弦长最长的点对（即圆的水平直径，长度 4 厘米）。总长度为 $4 + 3 + 3 = 10$ 厘米。

在样例 #2 中，第四和第五个点非常接近第三个点，但 $\mathbf{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$
  因此选择第一和第三个点获得最大长度。

样例测试集 2：注意存在三组点对并列产生第 9 长的琴弦。不同琴弦可以交叉，因为 Lauren 每次只演奏一个音符。

数据范围

• $1 \leq \mathbf{T} \leq 100$
• $\mathbf{N} = 150000$ 的用例不超过 10 个
• $5 \leq \mathbf{N} \leq 10^4$（当 $\mathbf{N} \neq 150000$ 时）
• $1 \leq \mathbf{R} \leq 10^9$
• $0 \leq \mathbf{D}_1$
• $\mathbf{D}_i < \mathbf{D}_{i+1}$（对所有 $i$）
• $\mathbf{D}_N < 360 \times 10^9$

测试集 1（15 分，可见判定）

• $\mathbf{L}_i$ 在 1 到 $10^9$ 之间独立均匀随机生成
• $\mathbf{K} = 1$

测试集 2（27 分，隐藏判定）

• $1 \leq \mathbf{L}_i \leq 10^9$（生成方式无限制）
• $\mathbf{K} = 10$