Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: lmio_2018_2et_metro_vyr.in

Rezultatų failas: lmio_2018_2et_metro_vyr.out

Jei norite pateikti savo sprendimą - prisijunkite.

Metro

Metro linijoje važiuoja T traukinių. Idealiu atveju, visi traukiniai būna išsidėstę vienodais atstumais – tokiu atveju sakome, kad eismas yra reguliarus. Tačiau dažnai, dėl įvairių priežasčių, traukiniai priartėja arba nutolsta vieni nuo kitų. Todėl karts nuo karto visų traukinių paprašoma sustoti ir palaukti kažkiek minučių. Šis procesas yra vadinamas reguliarizacija.

Užduotis

Jums žinomi atstumai tarp visų traukinių, matuojami minutėmis. Raskite, kiek minučių turi palaukti kiekvienas traukinys, kad eismas taptų reguliarus ir atstumas tarp visų gretimų traukinių būtų lygus lygiai M minučių.

Laikyti traukinius sustabdytus yra brangu, tad jei yra keli galimi atsakymai, išveskite tą, kuriame bendra laukiamo laiko suma yra mažiausia.

Pradiniai duomenys

Pirmoje eilutėje pateikti du sveikieji skaičiai: T –traukinių skaičius, ir M – pageidaujamas atstumas tarp visų gretimų traukinių.

Antroje eilutėje yra įrašyti T-1 skaičių m_1,m_2,...m_{T-1} – tai atstumai tarp visų gretimų traukinių metro linijoje.

Rezultatai

Išveskite T skaičių vienoje eilutėje – kiek minučių turi palaukti kiekvienas traukinys, kad eismas taptų reguliarus (visi atstumai būtų lygūs M).

Pavyzdžiai

Pradiniai duomenys Rezultatai Paaiškinimas 
3 5
4 3
 
0 1 3
 
Šiuo atveju pirmas traukinys gali pradėti judėti nesulaukęs. Antrasis turi palaukti vieną minutę, o trečiasis - 3
 
4 3
1 6 4
 
2 4 1 0
 
Pirmas traukinys turės palaukti 2 minutes, antrasis – 4 minutes, trečiasis – 1 minutę, o ketvirtasis gali pradėti judėti iš karto.
 
4 7
8 4 8
 
1 0 3 2
 







Ribojimai


1<T\\leq100000,1\\leqm_1,m_2,...m_{T-1}\\leq1000