Цар Прімонід організовує турнір, щоб знайти найсильнішого гладіатора в усіх землях. Загалом до Колізею прибули $N$ гладіаторів, щоб принести честь і славу своїм рідним містам. Кожен гладіатор починає з певним запасом життєвої сили (vitality). Життєва сила подібна до очок здоров'я тим, що відображає кількість шкоди, яку гладіатор може витримати, але вона також визначає кількість шкоди, якої він може завдати (оскільки для сильних ударів потрібна енергія).

Турнір складається з $K$ раундів. Кожного раунду цар шикує гладіаторів у шеренгу в порядку від найменшої до найбільшої залишкової життєвої сили, розв'язуючи нічиї випадковим чином. Цар Прімонід вважає, що справжня сила гладіатора полягає в його здатності тримати удар, тому він наказує першому гладіатору (тому, у кого залишилося найменше життєвої сили) завдати свого найсильнішого удару другому гладіатору. Цей удар віднімає життєву силу першого гладіатора від життєвої сили другого гладіатора. Після того як другий гладіатор приймає удар, він завдає свого найсильнішого удару (використовуючи свою нову, зменшену життєву силу) третьому гладіатору, і так далі. Цей процес повторюється, доки передостанній гладіатор не завдасть свого найсильнішого удару останньому гладіатору (який уже нікого не атакує).

Зверніть увагу, що в описаному вище процесі життєва сила гладіатора ніколи не може опуститися нижче нуля. (Гладіатор із нульовою життєвою силою завдає наступному гладіатору слабкого удару без жодної шкоди.)

Виведіть життєву силу кожного гладіатора після $K$ раундів турніру в порядку від першого до останнього гладіатора в шерензі.

Вхідні дані

Перший рядок вхідних даних містить два розділені пробілом цілі числа $N$ ($2 \le N \le 10^5$) та $K$ ($1 \le K \le 10^{18}$): кількість гладіаторів і кількість раундів у турнірі.

Наступний рядок вхідних даних містить $N$ розділених пробілами цілих чисел $v_1, v_2, \dots, v_N$ ($0 \le v_i \le 10^{18}$): початкову життєву силу гладіаторів.

Вихідні дані

Виведіть $N$ розділених пробілами цілих чисел: життєву силу гладіаторів наприкінці $K$-го раунду турніру в тому порядку, в якому гладіатори наразі стоять у шерензі.

Приклади

Вхідні дані 1

6 3
21 28 24 23 1 12

Вихідні дані 1

1 1 3 6 3 10

Вхідні дані 2

3 1000
8 2 10

Вихідні дані 2

0 0 2