Minimum Range Subset

Time limit2sMemory limit1024 MB

Summary

Given n numbers, choose k of them so that the gap between the largest and smallest chosen values is minimal, and print the subset.

Level: Medium4 of 10
Topics: Sorting, Sliding window
Solved: No attempts yet

Statement

At the Institute for Gifted Youngsters, Wolverine often struggled with Professor Xavier's courses. The strict lecturer demanded great quickness from his students and often set problems to test their minds. One of them was this: from a set of $n$ numbers, choose a subset of size $k$ so that the difference between the maximum and minimum numbers in the subset is as small as possible.

Wolverine did not want to solve it in his head, so he decided to write a program. Recently, while going through his archive of old programs, he found a bug in his implementation of this problem. He has no time to rewrite the program, so he asks you for help. Who else would you turn to when Magneto attacks the planet once again?

Input

The first line contains two integers $n$ and $k$ ( $2 \le k \le n \le 100000$ ), the size of the set and the size of the subset to choose. The second line contains $n$ integers $a_i$ ( $0 \le a_i \le 10^9$ ).

Output

Print $k$ numbers from the original set separated by spaces, such that the difference between the maximum and minimum of them is as small as possible.

Examples2

Example 1
Input
```
5 4
3 0 5 1 2
```
Expected output
```
0 1 2 3
```
Example 2
Input
```
7 3
8 8 9 13 1 5 10
```
Expected output
```
8 8 9
```