Kong Primonidas arrangerer en turnering for å finne den sterkeste gladiatoren i hele landet. Totalt har $N$ gladiatorer tatt veien til Colosseum for å bringe heder og ære tilbake til hjemstedene sine. Hver gladiator starter med en viss mengde vitalitet. Vitalitet ligner på helsepoeng ved at den gjenspeiler hvor mye skade en gladiator kan tåle, men den representerer også hvor mye skade de kan gjøre (ettersom det kreves energi for å gi kraftige slag).

Turneringen består av $K$ runder. I hver runde stiller kongen gladiatorene opp på rekke fra minst til mest gjenværende vitalitet, og avgjør uavgjort tilfeldig. Kong Primonidas mener at den sanne styrken til en gladiator ligger i evnen til å tåle juling, så han beordrer den første gladiatoren (den med lavest gjenværende vitalitet) til å gi sitt sterkeste slag til den andre gladiatoren. Dette slaget trekker den første gladiatorens vitalitet fra den andre gladiatorens vitalitet. Etter at den andre gladiatoren har tatt imot slaget, gir vedkommende sitt sterkeste slag (med sin nye, reduserte vitalitet) til den tredje gladiatoren, og så videre. Denne prosessen gjentas helt til den nest siste gladiatoren gir sitt sterkeste slag til den siste gladiatoren (som ikke får angripe noen).

Merk at i prosessen ovenfor kan en gladiators vitalitet aldri gå under null. (En gladiator med null i vitalitet gir et svakt slag uten skade til neste gladiator.)

Skriv ut vitaliteten til hver gladiator etter $K$ turneringsrunder, i rekkefølge fra den første til den siste gladiatoren i rekken.

Inndata

Den første linjen i inndata inneholder to mellomromseparerte heltall $N$ ($2 \le N \le 10^5$) og $K$ ($1 \le K \le 10^{18}$): antallet gladiatorer og antallet runder i turneringen.

Den neste linjen i inndata inneholder $N$ mellomromseparerte heltall $v_1, v_2, \dots, v_N$ ($0 \le v_i \le 10^{18}$): startvitaliteten til gladiatorene.

Utdata

Skriv ut $N$ mellomromseparerte heltall: vitaliteten til gladiatorene på slutten av den $K$-te runden i turneringen, i den rekkefølgen gladiatorene står i rekken.

Eksempler

Inndata 1

6 3
21 28 24 23 1 12

Utdata 1

1 1 3 6 3 10

Inndata 2

3 1000
8 2 10

Utdata 2

0 0 2