Safe
The Bank of Olympia has invited Petryk to test their latest security system. His challenge is to unlock the safe as quickly as possible by deciphering the code. The safe's central circle is surrounded by p natural numbers. To unlock it, each number must be replaced with another natural number such that when each number is added to the q-1 numbers that follow it, the sum equals the original number. For instance, if the numbers around the safe are 11, 12, 11, 9, 9, 9, 9 and q=5, the numbers should be adjusted to 1, 2, 3, 2, 3, 2, 1 to open the safe!
Task
Create a program that, given the initial configuration of the safe and the number q, restores one of the possible configurations that will unlock the safe.
Input
The first line of the input contains two natural numbers p and q, where (1 ≤ q ≤ p ≤ 10^4). Both p and q are prime numbers. The next line contains p natural numbers, each not exceeding 10^5 – representing the initial configuration of the safe.
Output
Output a single line containing p natural numbers, each not exceeding 10^9, that will unlock the safe. It is guaranteed that at least one such configuration exists. If there are multiple valid configurations, you may output any one of them.
Evaluation
Additionally, the following conditions are guaranteed:
For 30% of the tests: p ≤ 7, and there is a solution where all required numbers are ≤ 7.
For 60% of the tests: p ≤ 500, and there is a solution where all required numbers are ≤ 500.