Safe#7884
Olympia's national bank invited Petryk to test its newest security system. His task is to open the safe as quickly as possible by deciphering its code. Around the central circle of the safe are written natural numbers. To unlock the safe, each number must be replaced with another natural number so that, for every position, the sum of the number and the following q-1 numbers (in a circular manner) equals the original number at that position.
For example, if the numbers around the safe are 11, 12, 11, 9, 9, 9, 9 and q=5, the replacement numbers should be 1, 2, 3, 2, 3, 2, 1 so that the safe can be opened!
Write a program that, given the initial configuration of the safe and the number , reconstructs one possible configuration of numbers that will unlock the safe.
The first line of input contains two natural numbers and (1 \leq q \leq p \leq 10^4). Both and are prime numbers. The next line contains natural numbers not exceeding 10^5—the initial configuration of the safe.
Output a single line containing natural numbers, each not exceeding 10^9, corresponding to a configuration that will unlock the safe. It is guaranteed there is at least one solution. If there are multiple solutions, output any one of them.
Example 1
Additionally, the following conditions are guaranteed:
For 30% of the tests: p \leq 7, and there is a solution with all required numbers .
For 60% of the tests: p \leq 500, and there is a solution with all required numbers .