Kung Primonidas anordnar en turnering för att hitta den starkaste gladiatorn i hela riket. Totalt har $N$ gladiatorer tagit sig till Colosseum för att föra tillbaka ära och berömmelse till sina hemstäder. Varje gladiator börjar med en viss mängd vitalitet. Vitalitet liknar hälsopoäng såtillvida att den speglar hur mycket skada en gladiator kan ta, men den representerar också hur mycket skada gladiatorn kan utdela (eftersom det krävs energi för kraftfulla slag).

Turneringen består av $K$ rundor. I varje runda ställer kungen upp gladiatorerna på rad från minst till mest återstående vitalitet, och avgör lika fall slumpmässigt. Kung Primonidas anser att en gladiators sanna styrka ligger i förmågan att tåla stryk, så han beordrar den första gladiatorn (den med lägst återstående vitalitet) att utdela sitt hårdaste slag mot den andra gladiatorn. Detta slag subtraherar den första gladiatorns vitalitet från den andra gladiatorns vitalitet. Efter att den andra gladiatorn tagit emot slaget utdelar denne sitt hårdaste slag (med sin nya, sänkta vitalitet) mot den tredje gladiatorn, och så vidare. Denna process upprepas tills den näst sista gladiatorn utdelar sitt hårdaste slag mot den sista gladiatorn (som inte får attackera någon).

Observera att i processen ovan kan en gladiators vitalitet aldrig gå under noll. (En gladiator med noll i vitalitet utdelar ett svagt slag som inte gör någon skada på nästa gladiator.)

Skriv ut vitaliteten för varje gladiator efter $K$ turneringsrundor, i ordning från den första till den sista gladiatorn i raden.

Indata

Den första raden i indata innehåller två blankstegsseparerade heltal $N$ ($2 \le N \le 10^5$) och $K$ ($1 \le K \le 10^{18}$): antalet gladiatorer och antalet rundor i turneringen.

Nästa rad i indata innehåller $N$ blankstegsseparerade heltal $v_1, v_2, \dots, v_N$ ($0 \le v_i \le 10^{18}$): gladiatorernas startvitalitet.

Utdata

Skriv ut $N$ blankstegsseparerade heltal: gladiatorernas vitalitet i slutet av den $K$:te rundan i turneringen, i den ordning som gladiatorerna för närvarande står i raden.

Exempel

Indata 1

6 3
21 28 24 23 1 12

Utdata 1

1 1 3 6 3 10

Indata 2

3 1000
8 2 10

Utdata 2

0 0 2