Le roi Primonidas organise un tournoi afin de trouver le gladiateur le plus fort de toutes les contrées. Au total, $N$ gladiateurs se sont rendus au Colisée pour rapporter honneur et gloire à leur ville natale. Chaque gladiateur commence avec une certaine quantité de vitalité. La vitalité est similaire aux points de vie en ce qu'elle reflète la quantité de dégâts qu'un gladiateur peut encaisser, mais elle représente également la quantité de dégâts qu'il peut infliger (car il faut de l'énergie pour porter des coups puissants).

Le tournoi se déroule en $K$ manches. À chaque manche, le roi aligne les gladiateurs par ordre croissant de vitalité restante, en départageant les ex æquo au hasard. Le roi Primonidas estime que la véritable force d'un gladiateur réside dans sa capacité à encaisser les coups ; il ordonne donc au premier gladiateur (celui ayant la plus faible vitalité restante) de porter son coup le plus puissant au deuxième gladiateur. Ce coup soustrait la vitalité du premier gladiateur à celle du deuxième gladiateur. Après avoir encaissé le coup, le deuxième gladiateur porte son coup le plus puissant (en utilisant sa nouvelle vitalité réduite) au troisième gladiateur, et ainsi de suite. Ce processus se répète jusqu'à ce que l'avant-dernier gladiateur porte son coup le plus puissant au dernier gladiateur (qui, lui, n'attaque personne).

Notez que dans le processus ci-dessus, la vitalité d'un gladiateur ne peut jamais descendre en dessous de zéro. (Un gladiateur ayant une vitalité nulle porte un coup faible qui n'inflige aucun dégât au gladiateur suivant.)

Affichez la vitalité de chaque gladiateur après $K$ manches de tournoi, dans l'ordre du premier au dernier gladiateur de la file.

Entrée

La première ligne d'entrée contient deux entiers séparés par un espace $N$ ($2 \le N \le 10^5$) et $K$ ($1 \le K \le 10^{18}$) : le nombre de gladiateurs et le nombre de manches du tournoi.

La ligne suivante de l'entrée contient $N$ entiers séparés par des espaces $v_1, v_2, \dots, v_N$ ($0 \le v_i \le 10^{18}$) : la vitalité initiale des gladiateurs.

Sortie

Affichez $N$ entiers séparés par des espaces : la vitalité des gladiateurs à la fin de la $K$-ième manche du tournoi, dans l'ordre où les gladiateurs se tiennent actuellement dans la file.

Exemples

Entrée 1

6 3
21 28 24 23 1 12

Sortie 1

1 1 3 6 3 10

Entrée 2

3 1000
8 2 10

Sortie 2

0 0 2