Царь Примонид устраивает турнир, чтобы найти сильнейшего гладиатора во всех землях. Всего в Колизей прибыли $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