We've seen multiple sorting algorithms, implemented them, and used them to solve various problems. Here's another interesting sorting problem. You can work in any programming language of your choice - Python, C++, Java, or anything else you want. Let's get started!

# Problem Statement

We're given an array with n numbers. We need to choose K numbers from the array such that the difference between the maximum and the minimum values from the array is minimized.

**Constraints:** n \leq 1000000 and k \leq n.

# IO description

**Input description:** The first line contains the number of test cases T. Each test case consists of two lines. The first line has two numbers n (size of array) and k (number of numbers of choose). The second line has a list of n numbers separated by spaces (" ").

**Sample Input:**

25 2183 332 272 301 1905 3183 332 272 301 190

**Output description:** Output should contain T lines. Each line should contain the answer for the respective test case - the minimum difference between the maximum and minimum values for some k numbers from the input.

**Sample output**:

760

**Explanation:**

In the first test case, the set {183, 190} achieves a difference of 7. No other set of size 2 has a smaller difference.

In the second test case, the set {332, 272, 301} achieves a difference of 332 - 272 = 60. No other set of size 3 has a smaller difference.

# Submitting your solution

Once you are confidant of your solution, download the input file and run your code with the provided input. Then take the quiz!

# Progressive 'hint-by-hint' solution

Only look at the hints if you can't solve the problem for **at-least 20-minutes**. Read **only one hint** that you could not figure out on your own. Then spend **at-least 20-minutes** trying to solve the problem again.

Hint 1:

Hint 2:

# Full solution

The solution for this assignment is included at the end of the quiz. The code executes in ~2 seconds. If you implemented your solution in C++ or Java, you should expect your solution to run at-least 5x faster.