一幅详述宙斯最新心血来潮想法的神圣卷轴在赫尔墨斯面前展开：接下来的几千年将是向凡人赠送神圣礼物的时期。信使之神赫尔墨斯被赋予了送达这些礼物的任务。请注意，这些可不是普通的礼物，而是来自奥林匹斯工坊的精美工艺品：一架能奏出纯粹欢乐旋律的里拉琴，一支能写出深刻智慧言语的羽毛笔，等等。这 $N$ 件礼物中的每一件都是独一无二的，而且更复杂的是，每件礼物都有一个最佳送达日期，即其魔力最强大的那一天。但是，神圣的法律禁止在最佳送达日期之前送达礼物，以免凡人变得自满和骄纵。当然，所有的礼物都必须送达。

更具挑战性的是，赫尔墨斯虽然是奥林匹斯山上速度最快的神，但他总是极其忙碌。在管理天界邮政服务和裁判战车比赛之间，他知道自己最多只能抽出 $K$ 天时间来运送礼物（在这些天中的每一天，赫尔墨斯都可以运送任意数量的礼物）。此外，延迟送达会产生惩罚：对于每件礼物，惩罚是其实际送达日期与最佳送达日期之差的平方。如果里拉琴迟到了一两天，一个村庄可能会经历几个小时略微跑调的音乐。当然，这只是一个小麻烦。然而，如果里拉琴迟到了一个月或一年，后果要严重得多：整整一年的不和谐旋律，足以让最坚忍的音乐家发疯。潜在的混乱是巨大的。

这就是你需要出场的地方了，凡人朋友。肩负无数职责的赫尔墨斯需要帮手。你能否通过确定运送礼物的最佳日期来帮他规划神圣日程，从而使延迟送达惩罚的总和最小化？

输入格式

输入的第一行包含两个空格分隔的整数：

• $N$，礼物的数量；
• $K$，赫尔墨斯用于送礼的最大天数。

输入的第二行包含 $N$ 个空格分隔的整数 $d_i$，表示每件礼物的最佳送达日期。

输出格式

输出单行空格分隔的整数，其中第 $i$ 个元素是赫尔墨斯应该送达第 $i$ 件礼物的日期。如果存在多个最优解，任何一个都将被接受。

数据范围

• $1 \le N \le 5\,000$
• $1 \le K \le 20$
• 对于所有 $1 \le i \le N$，有 $0 \le d_i \le 1\,000\,000$

样例

输入样例 1

5 2
50 0 51 10 50

输出样例 1

51 10 51 10 51