König Primonidas veranstaltet ein Turnier, um den stärksten Gladiator im ganzen Land zu finden. Insgesamt haben sich $N$ Gladiatoren auf den Weg ins Kolosseum gemacht, um Ehre und Ruhm in ihre Heimatstädte zurückzubringen. Jeder Gladiator beginnt mit einer bestimmten Menge an Vitalität. Vitalität ähnelt Lebenspunkten darin, dass sie die Menge an Schaden widerspiegelt, die ein Gladiator einstecken kann, stellt aber gleichzeitig auch die Menge an Schaden dar, die er austeilen kann (da für kräftige Schläge Energie benötigt wird).

Das Turnier besteht aus $K$ Runden. In jeder Runde stellt der König die Gladiatoren in einer Reihe aufsteigend nach ihrer verbleibenden Vitalität auf, wobei Gleichstände zufällig aufgelöst werden. König Primonidas glaubt, dass die wahre Stärke eines Gladiatorsplateaus in seiner Fähigkeit liegt, Schläge einzustecken. Daher befiehlt er dem ersten Gladiator (demjenigen mit der geringsten verbleibenden Vitalität), dem zweiten Gladiator seinen stärksten Schlag zu versetzen. Dieser Schlag zieht die Vitalität des ersten Gladiators von der Vitalität des zweiten Gladiators ab. Nachdem der zweite Gladiator den Treffer eingesteckt hat, versetzt er (mit seiner neuen, verringerten Vitalität) dem dritten Gladiator seinen stärksten Schlag und so weiter. Dieser Vorgang wiederholt sich, bis der vorletzte Gladiator dem letzten Gladiator (der niemanden mehr angreifen darf) seinen stärksten Schlag versetzt.

Beachte, dass die Vitalität eines Gladiators beim obigen Vorgang niemals unter null fallen kann. (Ein Gladiator mit einer Vitalität von null versetzt dem nächsten Gladiator lediglich einen schwachen Schlag ohne Schaden.)

Gib die Vitalität jedes Gladiators nach $K$ Turnierrunden aus, in der Reihenfolge vom ersten bis zum letzten Gladiator in der Reihe.

Eingabe

Die erste Zeile der Eingabe enthält zwei durch Leerzeichen getrennte ganze Zahlen $N$ ($2 \le N \le 10^5$) und $K$ ($1 \le K \le 10^{18}$): die Anzahl der Gladiatoren und die Anzahl der Runden im Turnier.

Die nächste Zeile der Eingabe enthält $N$ durch Leerzeichen getrennte ganze Zahlen $v_1, v_2, \dots, v_N$ ($0 \le v_i \le 10^{18}$): die anfängliche Vitalität der Gladiatoren.

Ausgabe

Gib $N$ durch Leerzeichen getrennte ganze Zahlen aus: die Vitalität der Gladiatoren am Ende der $K$-ten Turnierrunde, in der Reihenfolge, in der die Gladiatoren aktuell in der Reihe stehen.

Beispiele

Eingabe 1

6 3
21 28 24 23 1 12

Ausgabe 1

1 1 3 6 3 10

Eingabe 2

3 1000
8 2 10

Ausgabe 2

0 0 2