Description

Adamma 是一位对温度感兴趣的气候科学家。她每分钟记录一次当前温度，得到一个整数序列：$x_{1}, x_{2}, \ldots, x_{\mathrm{N}}$。（Adamma 使用自己特殊的温标，而不是常见的摄氏度或开尔文，因此这些值可能很大也可能为负数！）她经常把这些温度绘制在电脑屏幕上。

今天早上，她决定计算这个序列的滑动平均值，以获得更平滑的曲线。她使用了大小为 $\mathbf{K}$ 的平滑窗口，这意味着她将 $\mathbf{N}$ 个温度值转换为 $(\mathbf{N}-\mathbf{K}+1)$ 个平均温度值：$s_{1}, s_{2}, \ldots, s_{\mathbf{N}-\mathbf{K}+1}$。每个 $s_{i}$ 是 $x_{i}, x_{i+1}, \ldots, x_{i+\mathbf{K}-1}$ 的平均值。原始的 $x_{i}$ 都是整数，但 $s_{i}$ 可能是小数。

不幸的是，Adamma 忘记保存原始的温度序列了！现在她想要回答另一个问题——原始序列中最大温度和最小温度的差是多少？换句话说，她需要计算 $\max \left\{x_{1}, \ldots, x_{\mathrm{N}}\right\}-\min \left\{x_{1}, \ldots, x_{\mathrm{N}}\right\}$。但她手头只有 $\mathrm{N}$、$\mathrm{K}$ 和平滑后的序列。

经过一番思考，Adamma 意识到这可能无法唯一确定，因为可能有多种原始序列都能产生相同的平滑序列。在这种情况下，她想知道所有可能的原始序列中，最大温度和最小温度的差的最小值是多少。

Input Format

输入的第一行为测试用例数 $\mathbf{T}$。接下来有 $\mathbf{T}$ 组测试用例，每组测试用例包含两行。第一行包含两个整数 $\mathrm{N}$ 和 $\mathbf{K}$，用空格分隔。第二行包含整数 $\operatorname{sum}_{1}, \operatorname{sum}_{2}, \ldots, \operatorname{sum}_{\mathrm{N}-\mathbf{K}+1}$，用空格分隔。$s_{i}$ 由 $\operatorname{sum}_{i} / \mathbf{K}$ 给出。

Output Format

对于每组测试用例，输出一行，格式为 "Case #x: y"，其中 $x$ 为测试用例编号（从 1 开始），$y$ 为最大温度和最小温度的最小可能差值。

3
10 2
1 2 3 4 5 6 7 8 9
100 100
-100
7 3
0 12 0 12 0

Case #1: 5
Case #2: 0
Case #3: 12

Hint

样例解释

在第 1 组测试用例中，平滑后的序列为：

能够得到最小差值的整数序列为：

注意，序列：

虽然也能得到相同的平滑序列且最大差值为 $4$，但这不是有效答案，因为原始温度必须为整数。

在第 2 组测试用例中，我们只知道 $100$ 个原始值的和为 $-100$。所有原始值都为 $-1$ 也是可能的，此时最大最小差为 $0$，这是最小可能的差值。

在第 3 组测试用例中，原始序列可能为：

数据范围

• $1 \leq \mathrm{T} \leq 100$。
• $2 \leq \mathbf{K} \leq \mathrm{N}$。
• $\operatorname{sum}_{i}$ 为 $-10000$ 到 $10000$ 之间的整数。

小数据范围（6 分）

• 时间限制：5 秒。
• $2 \leq \mathrm{N} \leq 100$。

大数据范围（7 分）

• 时间限制：10 秒。
• $2 \leq \mathrm{N} \leq 1000$。
• $2 \leq \mathbf{K} \leq 100$。

由 ChatGPT 4.1 翻译