题目描述

A celestial scroll, detailing Zeus’s latest whim unfurls before Hermes: the next few millennia will be a period of divine gifting for mortals. Hermes, the messenger god, is tasked with delivering these gifts. Not just any gifts, mind you, but exquisitely crafted items from the Olympian workshops: a lyre that plays melodies of pure joy, a quill that writes words of profound wisdom, and so on. Each of the $N$ gifts is unique, and, to complicate matters, each has an optimal delivery date, a day when its magic would be most potent. But a divine law forbids delivering gifts before their optimal delivery day, lest mortals become complacent and entitled. Of course, all gifts must be delivered.

Adding to the challenge, Hermes, despite being the fastest god on Olympus, is always extremely busy. Between managing the celestial postal service and refereeing chariot races, he knows that he can only dedicate at most $K$ days for the deliveries (each of those days, Hermes can deliver any number of gifts). Furthermore, late deliveries incur penalties: for each gift, the penalty is the square of the difference between its actual delivery day and its optimal delivery day. If a lyre is delivered a day or two late, a village might experience a few hours of slightly off-key music. A minor inconvenience, to be sure. However, if the lyre is delivered a month or a year late, the consequences are far more dire: a full year of discordant melodies, enough to drive even the most stoic musician to madness. The potential for chaos is immense.

And this is where you come in, mortal friend. Hermes, with his myriad responsibilities, could use a helping hand. Can you help him plan his divine calendar by determining the best days for delivering the gifts, so as to minimize the sum of late delivery penalties?

输入格式

On the first line of the input, two space-separated integers:

• $N$, the number of gifts;
• $K$, the maximum number of days Hermes dedicates to gifting.

On the second line, $N$ space-separated integers $d_i$, representing the optimal delivery date of each gift.

输出格式

A single line of space-separated integers, where the $i$-th element is the day when Hermes should deliver the $i$-th gift. If there are multiple optimal solutions, they will all be accepted.

5 2
50 0 51 10 50

51 10 51 10 51

提示

Limits

• $1 \le N \le 5,000$
• $1 \le K \le 20$
• $0 \le d_i \le 1,000,000$ for all $i \le N$