criptare

Захарел и Бронзарел често си поставят един на друг криптографски предизвикателства. Този път Захарел е криптирал редица от N неотрицателни цели числа a0, a1, ...,aN-1 по следния начин: той избира цяло положително число M и построява следната редица: bi = ai+a(i+1) mod N+a(i+2) mod N+...+a(i+M-1) mod N, след което пита Бронзарел, дали може да намери първоначалната редица a0, a1, ..., aN-1 ако знае новата редица и числото M.

Задача

Напишете програма, която да помогне на Бронзарел.

Вход

Първият ред на входния файл  criptare.in  съдържа две положителни цели числа, N M, разделени с интервал. Следващият ред съдържа N цели неотрицателни числа, разделени с интервали, представляващи редицата b0, b1, ..., bN-1.

Изход

Изходният файл  criptare.out  трябва да съдържа единствен ред с N неотрицателни цели числа, разделени с по един интервал, представляващи редицата  a0, a1, ..., aN-1. Макар, че може да има много решения, Вронзарел знае, че редицата криптирана от Захарел е лексикографски най-малкото решение.

Ограниения

1 <= M, N <= 50000
0 <= bi <= 109

Под
a mod b се разбира остатъка от делението на числото a  на числото b.
Съществуването на поне едно решение е гарантирано.
Редицата
a0, a1, ..., aN-1 съдържа неотрицателни числа (не непременно положителни).

Примери

Criptare.in

criptare.out

criptare.in

criptare.out

3 2
3 5 4

1 2 3

6 4
8 13 11 13 17 10

2 5 0 1 7 3

Ограничение за време: 0.1 секунди на тест

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

(Превод на български: Стоян Капралов)