408660: GYM103256 I HuronForces

Pachita is excited for the oncoming ICPC World Finals and is preparing his strategy to train for the competition.

A ladder is a list of $$$N$$$ problems, where the difficulty level of the $$$i$$$-th problem is represented by a positive integer $$$a_i$$$ (the greater $$$a_i$$$ is, the harder the $$$i$$$-th problem is). Initially, only the first problem is available to solve. Once the $$$i$$$-th problem is solved, the $$$(i+1)$$$-th problem becomes available.

With $$$K$$$ days left before the World Finals, Pachita wants to solve all the problems in the ladder of the popular site HuronForces. Every morning, Pachita will access the ladder and see if there is any problem available to solve, and if there any, he will solve it. Once he solves a problem, he can decide to continue solving the next problem or to stop for that day. Pachita has to solve all the problems exactly once before the World Finals and he may solve the last problem before or during the $$$K$$$-th day.

Once Pachita decides to stop solving problems for a certain day, he will look at the difficulty level that he solved the most and his motivation will increase by that level (if there are multiple such difficulty levels, his motivation will increase by the greatest such level). On the other hand, he will look at the difficulty level that he solved the least and his motivation will decrease by that level (if there are multiple such difficulty levels, his motivation will decrease by the lowest such level).

More formally, let's denote the motivation of Pachita by an integer $$$m$$$ (initially $$$m=0$$$). Let's say that the sequence $$$A'=a_i,a_{i+1},...,a_{j-1}, a_j$$$ represents the difficulty levels of the problems solved by Pachita a certain day and $$$f_l$$$ is the frequency of the level $$$l$$$ in $$$A'$$$. Let $$$x$$$ be the greatest difficulty level such that $$$f_x$$$ is the greatest among all $$$f_i$$$ values, and let $$$y$$$ be the lowest difficulty level such that $$$f_y$$$ is the lowest among all $$$f_i$$$ and $$$f_i > 0$$$, then $$$m := m + x - y$$$. For example, if Pachita solved problems of level $$$2,4,1,3,2,1$$$ a certain day, then $$$x=2$$$ and $$$y=3$$$ and his motivation will change by $$$x-y=-1$$$.

Help Pachita to find the $$$X$$$ best plans for his training, that is, the $$$X$$$ plans that gives him the best motivation at the end. Two plans are considered different if there exists a problem $$$i$$$ that Pachita solved during the $$$x$$$-th day in the first plan and during the $$$y$$$-th day in the second plan such that $$$x \neq y$$$.

The first line contains three integers $$$N$$$, $$$K$$$ and $$$X$$$ ($$$1 \leq N,K \leq 100$$$ and $$$1 \leq X \leq 10^6$$$) $$$-$$$ number of problems in list, days left before World Finals and the number of plans that Pachita wants to know.

The second line contains $$$N$$$ integers $$$a_1, a_2, ..., a_N$$$ ($$$1 \leq a_i \leq 10^9$$$) $$$-$$$ difficulty level of problems.

Print a single integer with $$$X$$$ integers $$$-$$$ the motivation of the best $$$X$$$ plans in non-increasing order. If there are less than $$$X$$$ possible plans, print $$$.$$$ in the remaining positions.

6 1 10
2 4 1 3 2 1

-1 . . . . . . . . . 

6 3 10
2 4 1 3 2 1

5 5 5 4 4 4 4 4 4 3 

6 5 10
2 4 1 3 2 1

5 5 5 4 4 4 4 4 4 4 

In the first example, there is one day before the Word Finals and Pachita has to solve all the problems during that day. The explanation of the change in his motivation for that day is written in the problem description.