criptare

Zaharel and Bronzarel often have encryption challenges amongst themselves. This time, Zaharel encrypted a sequence of N non-negative integers a₀, a₁, ...,a_N-1 as follows: he took a non-negative integer M and built the following sequence: b_i = a_i+a_{(i+1) mod N}+a_{(i+2) mod N}+...+a_{(i+M-1) mod N}; then he asked Bronzarel if he can determine the initial sequence a₀, a₁, ..., a_N-1 if he is given this new sequence as well as number M.

Task

Write a program that helps out Bronzarel.

Input Data

Line one of input file criptare.in contains the two positive integers, N M, separated by a single space. The next line contains N non-negative integers each separated by a single space, representing the sequence b₀, b₁, ..., b_N-1.

Output Data

Output file criptare.out will contain a single line with N non-negative integers separated by a single space, representing the sequence a₀, a₁, ..., a_N-1. Although there can be multiple solutions, Bronzarel knows that the sequence encrypted by Zaharel is the lexicographical minimum solution.

Restrictions

1 <= M, N <= 50000
0 <= b_i <= 10⁹
By a mod b we understand the remainder of a's division to b
The existence of at least one solution is guaranteed.
The sequence a₀, a₁, ..., a_N-1 must contain non-negative integers (not necessarily non-zero).

Examples

Time limit: 0.1 seconds/test

Mircea Paşoi
University of Bucharest, Mathematics & IT Department
bogdanpasoi@yahoo.com