## Lost array

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.

## Comments