Zaharel si Bronzarel
se intrec adesea in criptare. De data aceasta, Zaharel a criptat un sir
de N numere naturale a0,
a1, ...,aN-1 astfel: a luat un numar natural M
si a construit urmatorul sir: bi
= ai+a(i+1) mod N+a(i+2) mod N+...+a(i+M-1)
mod N; apoi, l-a intrebat pe Bronzarel daca poate sa determine
sirul initial a0, a1, ...,
aN-1daca i se da acest nou sir, precum si numarul
M.
Cerinta
Scrieti un program care
il ajuta pe Bronzarel.
Date de intrare
Pe prima linie a fisierului
de intrare criptare.in sunt
scrise cele doua numere naturale N M,
separate printr-un singur spatiu. Pe urmatoarea linie sunt scrise N
numere naturale separate printr-un singur spatiu, reprezentand sirul b0,
b1, ..., bN-1.
Date de iesire
Fisierul de iesire criptare.out
va contine o singura linie pe care vor fi scrise N
numere naturale separate prin cate un singur spatiu, reprezentand sirul a0,
a1, ..., aN-1. Desi pot exista mai multe solutii, Bronzarel
stie ca sirul criptat de Zaharel este cel minim lexicografic dintre toate
solutiile posibile.
Restrictii
1 <= M, N <= 50000
0 <= bi <= 109
Prin a mod b se intelege restul
impartirii lui a la b
Se garanteaza existenta a cel putin unei solutii.
Sirul a0, a1, ...,
aN-1trebuie sa contina numere naturale (nu neaparat
nenule).
Exemple
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
Mircea Paşoi
Universitatea Bucuresti, Facultatea de Matematica si Informatica bogdanpasoi@yahoo.com