题目描述

Ivcho 已经是一名大学生了，他需要完成自己的算法程序设计作业。由于他忙于网球训练，所以希望你来帮忙。

在这份作业中，给定一个数 k，他需要用它来评价不同的多重集合。

对于一个数的多重集合，定义它的 k-美丽值 为：将集合中的元素按非递减顺序排列后，第 1 个、第 k + 1 个、第 2k + 1 个、……元素之和。

另外，还给定一个长度为 n 的序列 a_i。Ivcho 从一个空多重集合开始，按顺序依次将 a 中的元素加入该多重集合，并且在每次加入之后，都要记录当前多重集合的 k-美丽值。

请你编写程序 kth，求出这 n 次加入操作后的 k-美丽值。

输入格式

第一行输入两个整数 n 和 k，表示元素个数以及取值位置间隔。

第二行输入 n 个整数 a_i。

输出格式

输出 n 行，第 i 行输出加入 a_i 后当前多重集合的 k-美丽值。

数据范围

• 1 \le n \le 10^5
• 1 \le k \le n
• |a_i| \le 10^9

子任务

只有当某个子任务中的所有测试都通过时，才能获得该子任务的分数。

样例

输入

6 3
5 6 1 1 4 7

输出

5
5
1
7
6
6

样例解释

加入 a_0 后，多重集合为 {5}，k-美丽值为 5。

加入 a_1 后，多重集合为 {5, 6}，k-美丽值为 5。

加入 a_2 后，多重集合为 {1, 5, 6}，k-美丽值为 1。

加入 a_3 后，多重集合为 {1, 1, 5, 6}，k-美丽值为 1 + 6。

加入 a_4 后，多重集合为 {1, 1, 4, 5, 6}，k-美丽值为 1 + 5。

加入 a_5 后，多重集合为 {1, 1, 4, 5, 6, 7}，k-美丽值为 1 + 5。