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 |
1 2 3 |
6
4 |
2 5 0 1 7 3 |
Ограничение за време: 0.1 секунди на тест
Mircea Paşoi
University of Bucharest, Mathematics & IT Department
bogdanpasoi@yahoo.com
(Превод на български: Стоян Капралов)