평활 창 (작은 데이터)

아다마는 기온을 연구하는 기후과학자다. 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$가 주어진다. 이어서 테스트 케이스마다 두 줄이 주어진다. 첫 줄에는 정수 $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 K \le N$
• $2 \le N \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$였을 수 있다.