Minimize Maximum Difference in Subarrays

Given an array of n integers, your task is to rearrange the array optimally so that the difference between the maximum and minimum elements within any contiguous subarray of length k is minimized. In other words, you need to find an arrangement such that:

minimize  \( \max_{\text{subarray of length } k} \big(\max(subarray) - \min(subarray) \big) \)

You are given multiple test cases. For each test case, print a single integer representing the minimal possible difference.

Note: The optimal strategy is to sort the array, and then consider all contiguous subarrays of length k.

inputFormat

The input is given via stdin and follows the format below:

T
n1 k1
a1 a2 ... an1
...
nT kT
a1 a2 ... anT

Where:

• T is the number of test cases.
• For each test case, the first line contains two integers: n (the size of the array) and k (the length of the subarray).
• The following line contains n integers corresponding to the elements of the array.

outputFormat

For each test case, output the minimal possible difference for any subarray of length k on a new line via stdout.

## sample

2
5 3
1 5 3 8 12
6 2
4 2 7 3 5 1

4
1

</p>