평활화 창

Adamma는 온도에 관심이 있는 기후 과학자이다. 그녀는 매분 현재 온도를 정수로 기록하여 긴 정수 목록 $x_{1}$, $x_{2}$, ..., $x_{N}$을 만든다. (Adamma는 섭씨나 켈빈처럼 익숙한 척도 대신 자신만의 특별한 온도 척도를 사용하므로, 값이 큰 음수일 수도 있다!) 그녀는 이 온도들을 컴퓨터 화면에 자주 그래프로 표시한다.

오늘 아침, 그녀는 더 매끄러운 그래프를 얻기 위해 이 목록의 이동 평균을 계산하기로 했다. 그녀는 크기가 K인 평활화 창을 사용했으며, 이는 N개의 온도로 이루어진 수열을 (N - K + 1)개의 평균 온도로 이루어진 수열 $s_{1}$, $s_{2}$, ..., $s_{N-K+1}$으로 변환했다는 뜻이다. 각 $s_{i}$은 값 $x_{i}$, $x_{i+1}$, ..., $x_{i+K-1}$의 평균이다. 원래의 $x_{i}$ 값은 모두 정수였지만, $s_{i}$ 중 일부는 분수일 수 있다.

안타깝게도 Adamma는 원래의 온도 수열을 저장하는 것을 잊었다! 이제 그녀는 다른 질문, 즉 가장 높은 온도와 가장 낮은 온도의 차이가 얼마였는지에 답하고 싶다. 다시 말해, 그녀는 최댓값{$x_{1}$, ..., $x_{N}$} - 최솟값{$x_{1}$, ..., $x_{N}$}을 계산해야 한다. 하지만 그녀에게는 N, K, 그리고 평활화된 수열만 있다.

얼마간 생각한 끝에, Adamma는 유효한 답이 여러 개일 수 있으므로 이것이 불가능할 수도 있다는 사실을 깨달았다. 그런 경우, 주어진 N과 K의 값으로 그녀의 평활화된 수열을 만들어 낼 수 있는 가능한 모든 원래 수열 가운데 가능한 가장 작은 답을 알고 싶다.

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100. 2 ≤ K ≤ N. $sum_{i}$는 -10000 이상 10000 이하의 정수이다.

소형 데이터 세트

시간 제한: 240초. 2 ≤ N ≤ 100.

대형 데이터 세트

시간 제한: 480초. 2 ≤ N ≤ 1000. 2 ≤ K ≤ 100.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어지며, 각 테스트 케이스는 두 줄로 이루어진다. 첫 번째 줄에는 공백 문자로 구분된 정수 N과 K가 주어진다. 두 번째 줄에는 공백 문자로 구분된 정숫값 $sum_{1}$, $sum_{2}$, ..., $sum_{N-K+1}$가 주어진다. $s_{i}$은 $sum_{i}$ / K로 주어진다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작한다), y는 가장 높은 온도와 가장 낮은 온도 사이의 가능한 가장 작은 차이이다.

사례 #1에서 평활화된 수열은 다음과 같다:

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

가장 작은 차이를 만드는 정수 수열은 다음과 같다:

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

다음 수열도 살펴보자:

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

이 수열은 최대 차이가 4인 동일한 평활화된 수열을 만들지만, 원래 온도들이 정수였다는 사실이 알려져 있으므로 유효한 답이 아니다.

사례 #2에서 알 수 있는 것은 100개의 원래 값의 합이 -100이었다는 것뿐이다. 원래 값이 모두 정확히 -1이었을 수도 있으며, 이 경우 가장 높은 온도와 가장 낮은 온도의 차이는 0이 된다. 이는 차이가 가질 수 있는 가장 작은 값이다!

사례 #3에서 원래 수열은 다음과 같았을 수 있다:

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