Primonídas konungur er að halda mót til að finna sterkasta skylmingaþræl allra landa. Alls hafa $N$ skylmingaþrælar lagt leið sína í Hringleikahúsið til að færa heimabæjum sínum heiður og dýrð. Hver skylmingaþræll byrjar með ákveðið magn af lífskrafti (vitality). Lífskraftur svipar til lífsstiga að því leyti að hann endurspeglar hversu mikinn skaða skylmingaþræll getur þolað, en hann táknar einnig hversu miklum skaða hann getur valdið (þar sem orku þarf í þung högg).

Mótið samanstendur af $K$ umferðum. Í hverri umferð raðar konungurinn skylmingaþrælunum í röð frá minnstu til mestu eftirstandandi lífskrafts, og sker úr um jafntefli af handahófi. Primonídas konungur trúir því að sannur styrkur skylmingaþræls felist í getu hans til að þola barsmíðar, svo hann skipar fyrsta skylmingaþrælnum (þeim sem hefur minnstan lífskraft eftir) að greiða öðrum skylmingaþrælnum sitt sterkasta högg. Þetta högg dregur lífskraft fyrsta skylmingaþrælsins frá lífskrafti annars skylmingaþrælsins. Eftir að annar skylmingaþrællinn tekur við högginu greiðir hann þriðja skylmingaþrælnum sitt sterkasta högg (með nýja, lækkaða lífskraftinum sínum), og svo framvegis. Þetta ferli endurtekur sig þar til næstsíðasti skylmingaþrællinn greiðir síðasta skylmingaþrælnum sitt sterkasta högg (en sá síðasti fær ekki að ráðast á neinn).

Takið eftir að í ferlinu hér að ofan getur lífskraftur skylmingaþræls aldrei farið niður fyrir núll. (Skylmingaþræll með engan lífskraft greiðir næsta skylmingaþræl máttlaust högg sem veldur engum skaða.)

Prentið lífskraft hvers skylmingaþræls eftir $K$ umferðir mótsins, í röð frá fyrsta til síðasta skylmingaþræls í röðinni.

Inntak

Fyrsta lína inntaksins inniheldur tvær heiltölur aðskildar með bili, $N$ ($2 \le N \le 10^5$) og $K$ ($1 \le K \le 10^{18}$): fjölda skylmingaþræla og fjölda umferða í mótinu.

Næsta lína inntaksins inniheldur $N$ heiltölur aðskildar með bili, $v_1, v_2, \dots, v_N$ ($0 \le v_i \le 10^{18}$): upphaflegan lífskraft skylmingaþrælanna.

Úttak

Prentið $N$ heiltölur aðskildar með bili: lífskraft skylmingaþrælanna í lok $K$-tu umferðar mótsins, í þeirri röð sem skylmingaþrælarnir standa í röðinni á þeim tímapunkti.

Dæmi

Inntak 1

6 3
21 28 24 23 1 12

Úttak 1

1 1 3 6 3 10

Inntak 2

3 1000
8 2 10

Úttak 2

0 0 2