Lost array

Points: 100 (partial)
Time limit: 1.0s
Python 3 8.0s
Memory limit: 256M

Author:
Problem type

In this problem an array $$A$$ of $$N$$ integers (possibly negative) is hidden from you. We will give you instead an array $$S$$ such that $$S_i = \sum_{j = 0}^{k-1} A_{i+j}$$. We want you to output the difference between the largest and smallest elements of $$A$$.

Because there is a lot of possible answers, we want you to output the one minimizing that difference.

Input Specification

The first line of the input file contains one integer $$1 \leq T \leq 30$$: the number of test cases.

Each test case starts with a line with two integers $$N$$ and $$K$$ ($$1\leq K \leq N \leq 10^5$$).

The second line contains $$N - K + 1$$ space separated integers $$S_i$$ ($$-10^6 \leq S_i \leq 10^6$$).

Output Specification

For each test case output one line containing the answer to the problem.

Scoring

• ($$30$$ points) $$N ≤ 100$$.
• ($$30$$ points) $$N ≤ 1000$$.
• ($$40$$ points) No additional constraint.

Sample Input

2
5 2
1 0 0 1
4 3
1 0

Sample Output

1
1

Notes

One possible array $$A$$ corresponding to the first test case is : $$[1,0,0,0,1]$$ and to the second one : $$[1,0,0,0]$$.

The array $$[2,0,-1,1]$$ corresponds to the array $$S$$ of the second sample, but it does not minimize the difference between the largest and smallest elements.