평활 창 (라지)

아담마는 기온을 연구하는 기후 과학자다. 1분마다 현재 기온을 정수로 적어 두어서 긴 정수 목록 $x_1, x_2, \dots, x_N$을 만든다. 섭씨나 켈빈 같은 익숙한 눈금 대신 자기만의 온도 눈금을 쓰기 때문에 값이 아주 클 수도 있고 음수일 수도 있다. 아담마는 이 기온을 컴퓨터 화면에 자주 그린다.

오늘 아침 아담마는 그래프를 더 매끄럽게 만들려고 이 목록의 이동 평균을 계산했다. 크기가 $K$인 평활 창을 써서 기온 $N$개를 평균 기온 $N - K + 1$개 $s_1, s_2, \dots, s_{N-K+1}$로 바꿨다. 각 $s_i$는 $x_i, x_{i+1}, \dots, x_{i+K-1}$의 평균이다. 원래 값 $x_i$는 모두 정수지만 일부 $s_i$는 분수일 수 있다.

그런데 아담마는 원래 기온 목록을 저장하지 않았다. 지금 알고 싶은 값은 가장 높은 기온과 가장 낮은 기온의 차이, 즉 $\max\{x_1, \dots, x_N\} - \min\{x_1, \dots, x_N\}$이다. 남아 있는 자료는 $N$과 $K$, 그리고 평활한 수열뿐이다.

같은 평활 수열을 만드는 원래 수열이 여러 개일 수 있어서 이 차이는 하나로 정해지지 않는다. 그래서 아담마는 주어진 $N$, $K$, 평활 수열과 맞아떨어지는 모든 정수 수열 중에서 차이가 가장 작은 값을 구하려고 한다.

첫째 줄에 테스트 케이스 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어지며 각각 두 줄로 이루어진다. 첫째 줄에는 정수 $N$과 $K$가 공백으로 구분되어 주어진다. 둘째 줄에는 정수 $\mathrm{sum}_1, \mathrm{sum}_2, \dots, \mathrm{sum}_{N-K+1}$이 공백으로 구분되어 주어진다. $s_i$는 $\mathrm{sum}_i / K$와 같다.

제한

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

각 테스트 케이스마다 "Case #x: y" 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 가장 높은 기온과 가장 낮은 기온의 차이 중 가능한 최솟값이다.

첫 번째 예제에서 평활한 수열은 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지만, 각 항이 정수가 아니므로 원래 수열이 될 수 없다.

두 번째 예제에서 알 수 있는 사실은 원래 값 100개의 합이 -100이라는 것뿐이다. 100개가 모두 -1이면 차이는 0이고, 이보다 작은 차이는 없다.

세 번째 예제에서 원래 수열은 -4, 8, -4, 8, -4, 8, -4일 수 있다.