Smoothing Window (Large)

Adamma is a climate scientist who studies temperature. Every minute she writes down the current temperature as an integer, which builds a long list of integers $x_1, x_2, \dots, x_N$. She uses her own temperature scale instead of a familiar one such as Celsius or Kelvin, so the values can be large and they can be negative. She often plots these temperatures on her computer 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 values $x_i$ are all integers, but some $s_i$ can be fractional.

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

Several original sequences can produce the same smoothed sequence, so that difference is not determined. Adamma therefore asks for the smallest difference over every integer sequence that matches the given $N$, $K$, and smoothed values.

The first line contains the number of test cases $T$. Then $T$ test cases follow, and each one 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$ equals $\mathrm{sum}_i / K$.

Limits

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

For each test case, print one line in 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 sample case 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 its entries are not integers, so it is not a valid original sequence.

In the second sample case the only known fact is that the 100 original values add up to -100. Every value can be exactly -1, and then the difference is 0. No difference is smaller than that.

In the third sample case the original sequence can be -4, 8, -4, 8, -4, 8, -4.