Smoothing Window (Small)

Adamma is a climate scientist who studies temperature. Every minute she records the current temperature as an integer, which gives a long list of integers $x_1, x_2, \dots, x_N$. Adamma uses her own temperature scale instead of a familiar one such as Celsius or Kelvin, so the values can be large and negative. She often plots these temperatures on her screen.

This morning she computed a sliding average of the list to get a smoother plot. She used a smoothing window of size $K$, which turns the sequence of $N$ temperatures into a sequence of $N - K + 1$ average temperatures $s_1, s_2, \dots, s_{N-K+1}$. Each $s_i$ is the average of $x_i, x_{i+1}, \dots, x_{i+K-1}$. The original $x_i$ were all integers, but some $s_i$ may be fractional.

Adamma forgot to save the original sequence of temperatures. Now she wants a different quantity: the difference between the largest and the smallest temperature, $\max\{x_1, \dots, x_N\} - \min\{x_1, \dots, x_N\}$. All she still has is $N$, $K$, and the smoothed sequence.

Several original sequences may produce the same smoothed sequence, so this difference is not always determined. In that case Adamma wants the smallest difference over every integer sequence that produces her smoothed sequence with the given $N$ and $K$.

The first line contains the number of test cases $T$. Each test case takes two lines. The first line contains the integers $N$ and $K$ separated by a space. The second line contains the integers $\mathrm{sum}_1, \mathrm{sum}_2, \dots, \mathrm{sum}_{N-K+1}$ separated by spaces, where $s_i = \mathrm{sum}_i / K$.

Limits

• $1 \le T \le 100$
• $2 \le K \le N$
• $2 \le N \le 100$
• $-10000 \le \mathrm{sum}_i \le 10000$

For each test case, print one line of the form Case #x: y, where x is the test case number starting from 1 and y is the smallest possible difference between the largest and the smallest temperature.

In the first case of the example 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$. The sequence $0.5, 0.5, 1.5, 1.5, 2.5, 2.5, 3.5, 3.5, 4.5, 4.5$ produces the same smoothed sequence with a difference of 4, but it is not a valid answer because the original temperatures are known to be integers.

In the second case the only known fact is that the sum of the 100 original values is $-100$. All of them may be exactly $-1$, and then the difference is 0, which is as small as a difference gets.

In the third case the original sequence could have been $-4, 8, -4, 8, -4, 8, -4$.