Description

2022年5月底的这一天绍兴出台抗疫新的政策，要求每个绍兴居民一周内至少做一次核酸，否则健康码将变成黄码。乘坐公共交通、出入大型商场等地必须持有72小时核酸证明！于是当天各个核酸点都排起了长队……

由于天气炎热，每个核酸检测点还配备了移动降温设备。为了使设备尽可能发挥作用，应该选择一个距离所有排队的人距离之和最小的位置去放置，这样的降温效果最好。此外随着时间的推移，排在最后的那个人总会有些不耐烦，会放弃排队回家睡觉。每次发生这样的事情，降温设备的位置都会调整到新的最佳位置。

Input Format

第一行输入两个整数N和M(1<=M<=N)，分别表示某一时刻排队人数，以及放弃排队的人数(注意每次都是最后的那个人放弃)。

接下来一行N个整数ai，描述排队的每个人距离检测点的距离（注意这N个数不一定是排好序的）。

Output Format

输出共包括M+1 行，分别表示该时刻的排队人与设备的最小距离之和

5 2
5 1 3 5 2

7
5
2

Hint

30%数据：1≤M≤N≤1000

100%数据：1≤N≤10^6，1≤M≤5×10^4，1≤ai≤10^5