ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Open Ural SU Championship 2010

About     Problems     Submit solution     Judge status     Standings
Contest is over

J. Nuclear Arms Race

Time limit: 0.5 second
Memory limit: 64 MB
Western and Eastern Cuckooland are close to the outbreak of war. Superpowers are competing for supremacy in nuclear warfare to achieve dominance in the military sphere. Unfortunately, production and stockpiling of nuclear warheads are very expensive and can easily undermine the budgets of both countries.
Military analysts and economists of Western Cuckooland have provided a report according to which the country will be safe and the budget will be stable, if by the end of the i-th month there would be exactly ai warheads stockpiled in warehouses. The president ordered to adhere to these figures, so the plants in Western Cuckooland produce or dispose the necessary amount of warheads each month.
But the intelligence of Eastern Cuckooland is great! At the begining of the i-th month the spies from Eastern Cuckooland get access to the plans of Western Cuckooland for the next m months (that is, the numbers ai, ai + 1, …, ai + m − 1) and send them home. When dictator of Eastern Cuckooland receives this information, he immediately gives the order to change the current number of warheads in warehouses in Eastern Cuckooland by a number xi. He chooses xi, in such a way that if Eastern Cuckooland would change the number of warheads by xi during m months, it would have not less warheads than Western Cuckooland by the end of every month. The dictator also cares about the country's budget, therefore, he chooses the minimal possible xi.
Determine what orders the dictator of Eastern Cuckooland will give during the first n months. You can assume that at the beginning of the first month, neither Western nor Eastern Cuckooland posess nuclear arsenal.


The first line contains space-separated integers n and m (1 ≤ n ≤ 10000; 1 ≤ m ≤ 50). The second line contains space-separated integers a1, …, an + m − 1 (0 ≤ ai ≤ 105), which are the plans of the Western Cuckooland.


Output a list of space-separated integers x1, …, xn. Number xi corresponds to the order the dictator of Eastern Cuckooland will give at the begining of the i-th month.


4 3
0 0 4 2 1 0
2 1 1 -1


Problem illustration
Problem Author: Pavel Atnashev
Problem Source: XV Open USU Championship
To submit the solution for this problem go to the Problem set: 1783. Nuclear Arms Race