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 *a*_{i} 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
*a*_{i}, *a*_{i + 1}, …,
*a*_{i + 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 *x*_{i}. He chooses *x*_{i},
in such a way that if Eastern Cuckooland would change the number of warheads by
*x*_{i} 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 *x*_{i}.

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.

### Input

The first line contains space-separated integers *n* and *m*
(1 ≤ *n* ≤ 10000; 1 ≤ *m* ≤ 50).
The second line contains space-separated integers *a*_{1}, …,
*a*_{n + m − 1}
(0 ≤ *a*_{i} ≤ 10^{5}), which are
the plans of the Western Cuckooland.

### Output

Output a list of space-separated integers *x*_{1}, …, *x*_{n}.
Number *x*_{i} corresponds to the order the dictator of Eastern Cuckooland
will give at the begining of the *i*-th month.

### Sample

input | output |
---|

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

### Notes

**Problem Author: **Pavel Atnashev

**Problem Source: **XV Open USU Championship