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.
0 0 4 2 1 0
2 1 1 -1
Problem Author: Pavel Atnashev
Problem Source: XV Open USU Championship