Adamma is a climate scientist interested in temperature. Every minute,
she records the current temperature as an integer, creating a long list
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 K, which means that she converted the sequence of N temperatures into a sequence of
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
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 N and K.
The first line of the input gives the number of test cases, T. T test cases follow; each test case consists of two lines. The first line contains integers N and K separated by a space character. The second line contains integer values
For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the smallest possible difference between the largest and smallest temperature.
1 ≤ T ≤ 100.
2 ≤ K ≤ N.
The sumi will be integers between -10000 and 10000, inclusive.
2 ≤ N ≤ 100.
2 ≤ N ≤ 1000.
2 ≤ K ≤ 100.
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