Król Primonidas organizuje turniej mający wyłonić najsilniejszego gladiatora we wszystkich krainach. Łącznie $N$ gladiatorów przybyło do Koloseum, aby przynieść honor i chwałę swoim rodzinnym miastom. Każdy gladiator zaczyna z pewną ilością witalności. Witalność przypomina punkty zdrowia, ponieważ odzwierciedla ilość obrażeń, jakie gladiator może przyjąć, ale reprezentuje również ilość obrażeń, jakie może zadać (gdyż do silnych ciosów potrzebna jest energia).

Turniej składa się z $K$ rund. W każdej rundzie król ustawia gladiatorów w szeregu od najmniejszej do największej pozostałej witalności, rozstrzygając remisy losowo. Król Primonidas wierzy, że prawdziwa siła gladiatora tkwi w jego zdolności do przyjmowania ciosów, dlatego rozkazuje pierwszemu gladiatorowi (temu o najmniejszej pozostałej witalności) zadać najsilniejszy cios drugiemu gladiatorowi. Cios ten odejmuje witalność pierwszego gladiatora od witalności drugiego gladiatora. Po tym, jak drugi gladiator przyjmie uderzenie, zadaje on swój najsilniejszy cios (używając swojej nowej, obniżonej witalności) trzeciemu gladiatorowi i tak dalej. Proces ten powtarza się aż do momentu, gdy przedostatni gladiator zada swój najsilniejszy cios ostatniemu gladiatorowi (który nie ma już kogo zaatakować).

Zauważ, że w powyższym procesie witalność gladiatora nigdy nie może spaść poniżej zera. (Gladiator o zerowej witalności zadaje słaby cios niepowodujący żadnych obrażeń następnemu gladiatorowi).

Wypisz witalność każdego gladiatora po $K$ rundach turnieju, w kolejności od pierwszego do ostatniego gladiatora w szeregu.

Wejście

Pierwszy wiersz wejścia zawiera dwie oddzielone spacją liczby całkowite $N$ ($2 \le N \le 10^5$) oraz $K$ ($1 \le K \le 10^{18}$): liczbę gladiatorów oraz liczbę rund w turnieju.

Kolejny wiersz wejścia zawiera $N$ oddzielonych spacjami liczb całkowitych $v_1, v_2, \dots, v_N$ ($0 \le v_i \le 10^{18}$): początkową witalność gladiatorów.

Wyjście

Wypisz $N$ oddzielonych spacjami liczb całkowitych: witalność gladiatorów na koniec $K$-tej rundy turnieju, w kolejności, w jakiej gladiatorzy aktualnie stoją w szeregu.

Przykład

Wejście 1

6 3
21 28 24 23 1 12

Wyjście 1

1 1 3 6 3 10

Wejście 2

3 1000
8 2 10

Wyjście 2

0 0 2