题目描述

Adamma is a climate scientist interested in temperature. Every minute, she records the current temperature as an integer, creating a long list of integers: $x_{1}, x_{2}, \ldots, x_{\mathrm{N}}$. (Adamma uses her own special temperature scale rather than a familiar one like Celsius or Kelvin, so it's possible for the values to be large and negative!) She often plots these temperatures on her computer screen.

This morning, she decided to compute a sliding average of this list in order to get a smoother plot. She used a smoothing window of size $\mathbf{K}$, which means that she converted the sequence of $\mathbf{N}$ temperatures into a sequence of $(\mathbf{N}-\mathbf{K}+1)$ average temperatures: $s_{1}, s_{2}, \ldots, s_{\mathbf{N}-\mathbf{K}+1}$. Each $s_{i}$ is the average of the values $x_{i}, x_{i+1}, \ldots, x_{i+\mathbf{K}-1}$. The original $x_{i}$ values were all integers, but some of the $s_{i}$ may be fractional.

Unfortunately, Adamma forgot to save the original sequence of temperatures! And now she wants to answer a different question -- what was the difference between the largest temperature and the smallest temperature? In other words, she needs to compute $\max \left\{x_{1}, \ldots, x_{\mathrm{N}}\right\}-\min \left\{x_{1}, \ldots, x_{\mathrm{N}}\right\}$. But she only has $\mathrm{N}, \mathrm{K}$, and the smoothed sequence.

After some thinking, Adamma has realized that this might be impossible because there may be several valid answers. In that case, she wants to know the smallest possible answer among all of the possible original sequences that could have produced her smoothed sequence with the given values of $\mathrm{N}$ and $\mathrm{K}$.

输入格式

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow; each test case consists of two lines. The first line contains integers $\mathrm{N}$ and $\mathbf{K}$ separated by a space character. The second line contains integer values $\operatorname{sum}_{1}, \operatorname{sum}_{2}, \ldots, \operatorname{sum}_{\mathrm{N}-\mathbf{K}+1}$, separated by space characters. $s_{i}$ is given by $\operatorname{sum}_{i} / \mathbf{K}$.

输出格式

For each test case, output one line containing "Case #x: y", where $\mathrm{x}$ is the test case number (starting from 1) and $\mathrm{y}$ is the smallest possible difference between the largest and smallest temperature.

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

提示

Sample Explanation

In Case #1, the smoothed sequence is:

$$0.5, 1.0, 1.5, 2.0, 2.5, 3.0, 3.5, 4.0, 4.5$$

The integer sequence that gives the smallest difference is:

$$0, 1, 1, 2, 2, 3, 3, 4, 4, 5$$

Note that the sequence:

$$0.5, 0.5, 1.5, 1.5, 2.5, 2.5, 3.5, 3.5, 4.5, 4.5$$

Would give the same smoothed sequence with a maximum difference of $4$, but this is not a valid answer because the original temperatures are known to have been integers.

In Case #2, all we know is that the sum of the $100$ original values was $-100$. It's possible that all of the original values were exactly $-1$, in which case the difference between the largest and smallest temperatures would be $0$, which is as small as differences get!

In Case #3, the original sequence could have been:

$$-4, 8, -4, 8, -4, 8, -4$$

Sample Explanation

• $1 \leq \mathrm{T} \leq 100 .$
• $2 \leq \mathbf{K} \leq \mathrm{N} .$
• The $\operatorname{sum}_{i}$ will be integers between -10000 and 10000, inclusive.

Small dataset(6 Pts)

• Time limit: 240 5 seconds.
• $2 \leq \mathrm{N} \leq 100 .$

Large dataset(7 Pts)

• Time limit: 480 10 seconds.
• $2 \leq \mathrm{N} \leq 1000 .$
• $2 \leq \mathbf{K} \leq 100 .$