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.

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

Output a list of space-separated integers x₁, …, x_n. Number x_i corresponds to the order the dictator of Eastern Cuckooland will give at the begining of the i-th month.