Adamma là một nhà khoa học khí hậu quan tâm đến nhiệt độ. Mỗi phút, cô ghi lại nhiệt độ hiện tại dưới dạng số nguyên, tạo thành một danh sách dài \(x_1,x_2,\ldots,x_N\). Adamma dùng thang nhiệt độ riêng thay vì những thang quen thuộc như Celsius hay Kelvin, nên các giá trị có thể rất lớn và âm. Cô thường vẽ đồ thị các nhiệt độ này trên màn hình máy tính.

Sáng nay, Adamma quyết định tính trung bình trượt của danh sách để có một đồ thị mượt hơn. Cô dùng cửa sổ làm mượt kích thước \(K\), nghĩa là biến dãy \(N\) nhiệt độ thành dãy \(N-K+1\) nhiệt độ trung bình \(s_1,s_2,\ldots,s_{N-K+1}\). Mỗi \(s_i\) là trung bình của \(x_i,x_{i+1},\ldots,x_{i+K-1}\). Các giá trị \(x_i\) ban đầu đều là số nguyên, nhưng một số \(s_i\) có thể là phân số.

Không may, Adamma quên lưu dãy nhiệt độ ban đầu! Bây giờ cô muốn trả lời một câu hỏi khác: chênh lệch giữa nhiệt độ lớn nhất và nhỏ nhất là bao nhiêu? Nói cách khác, cô cần tính

Nhưng cô chỉ còn \(N\), \(K\) và dãy đã làm mượt.

Sau khi suy nghĩ, Adamma nhận ra có thể không xác định được duy nhất vì có nhiều dãy ban đầu hợp lệ. Trong trường hợp đó, cô muốn biết đáp án nhỏ nhất trong tất cả các dãy ban đầu có thể tạo ra dãy làm mượt với \(N\) và \(K\) đã cho.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test gồm hai dòng. Dòng đầu chứa hai số nguyên \(N\), \(K\) cách nhau bởi dấu cách. Dòng thứ hai chứa các số nguyên \(\mathrm{sum}_1,\mathrm{sum}_2,\ldots,\mathrm{sum}_{N-K+1}\) cách nhau bởi dấu cách, trong đó \(s_i=\mathrm{sum}_i/K\).

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1), còn \(y\) là chênh lệch nhỏ nhất có thể giữa nhiệt độ lớn nhất và nhỏ nhất.

Ràng buộc

• \(1\le T\le100\).
• \(2\le K\le N\).
• Mỗi \(\mathrm{sum}_i\) là một số nguyên trong đoạn \([-10000,10000]\).

Phân nhóm

• Tập nhỏ: \(2\le N\le100\).
• Tập lớn: \(2\le N\le1000\); \(2\le K\le100\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

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

Nguồn

Google Code Jam 2015, Vòng 3, bài Smoothing Window.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.