Optimal Signal Station Placement

You are given a road with N houses located on it. The houses may share the same coordinate. Due to limited conditions, the authorities can only construct k signal stations (with k being less than N), and they want to minimize the sum of the "unreasonable values" of these stations. The unreasonable value of a signal station placed at position x is defined as the sum of its distances to every house, that is:

where a_i denotes the coordinate of the i-th house. Since each signal station incurs the cost f(x) independently, the overall cost is $$F=\sum_{\text{station}\; x}\; f(x).$$

Your task is to choose k distinct integer positions (no two stations can be placed at the same point) such that the total cost F is minimized. If there are multiple optimal solutions, output the lexicographically smallest one (i.e. the chosen positions in increasing order are as small as possible).

Note: The optimal strategy is to choose the k integers which are closest (in terms of the cost function f(x)) to the median of the house positions.

inputFormat

The input consists of two lines:

The first line contains two integers N and k (with N > k), representing the number of houses and the number of signal stations to be built.

The second line contains N integers, representing the positions of the houses along the road.

outputFormat

Output k distinct integer positions in increasing order (separated by spaces) that represent the optimal locations to construct the signal stations minimizing the total cost. The cost for a station placed at position x is given by

sample

3 2
1 2 100

1 2