E. Очередь в поезде
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В вагоне поезда на $$$n$$$ местах сидят $$$n$$$ людей, человек с номером $$$i$$$ сидит на месте с номером $$$i$$$. Места пронумерованы слева направо от $$$1$$$ до $$$n$$$. Поездка долгая, поэтому каждый человек в какой-то момент проголодается и захочет заварить лапшу быстрого приготовления кипятком, $$$i$$$-й человек захочет выйти за кипятком ровно в начале $$$t_i$$$-й минуты.

Бак с кипятком находится левее $$$1$$$-го места за дверью. Поскольку баком одновременно может пользоваться не более одного человека, люди стоящие у бака образуют очередь в порядке, в котором они подошли к баку. Как только человек заканчивает наливать кипяток, следующий за ним в очереди человек (если такой есть) начинает наливать кипяток себе. Каждый человек наливает себе кипяток ровно $$$p$$$ минут.

Люди не любят просто так стоять в очереди. После того, как человек на месте с номером $$$i$$$ захочет сходить за кипятком, в начале каждой минуты (включая $$$t_i$$$-ю минуту) он будет оценивать размер очереди, в которую он попадёт, если отправится за кипятком прямо сейчас, а именно он посмотрит на все места с номерами от $$$1$$$ до $$$i - 1$$$. Если хотя бы одно из этих мест пусто, то есть в очереди возле бака есть люди с номерами, меньшими $$$i$$$, человек с номером $$$i$$$ решит, что очередь слишком большая и останется на своём месте до начала следующей минуты. В противном случае человек с номером $$$i$$$ тут же встанет со своего места и приготовится идти за кипятком. Однако если человек с номером $$$j$$$ ($$$j \lt i$$$) также решит отправиться за кипятком в этот же момент, человек с номером $$$i$$$ это увидит, сядет обратно на своё место и снова будет ждать начала следующей минуты. Таким образом, в начале каждой минуты не более одного человека отправится за кипятком. Обратите внимание, что конструкция вагона такова, что люди видят только места перед собой, но не видят бак и очередь перед ним, поэтому могут принимать решения только исходя из наличия людей на местах перед ними.

Временем перемещения людей по вагону можно принебречь. Например, если человек проголодался в начале $$$t$$$-й минуты, и в этот момент очередь к баку была пуста, то он окажется у бака в начале $$$t$$$-й минуты, закончит наливать воду в конце минуты с номером $$$t + p - 1$$$, и в начале минуты с номером $$$t + p$$$ уже будет сидеть на своём месте.

Для каждого человека определите, на какой минуте он вернётся на своё место с кипятком для лапши.

Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$p$$$ ($$$1 \leq n \leq 100\,000$$$, $$$1 \leq p \leq 10^9$$$) — количество людей в вагоне и количество минут, которое каждый человек тратит на использование бака.

Во второй строке содержатся $$$n$$$ целых чисел $$$t_1, t_2, \dots, t_n$$$ ($$$0 \leq t_i \leq 10^9$$$), $$$i$$$-е из которых означает, что $$$i$$$-й человек проголодается в начале $$$t_i$$$-й минуты.

Выходные данные

Выведите $$$n$$$ целых чисел, $$$i$$$-е из которых — номер минуты, на которой $$$i$$$-й человек вернётся на своё место с кипятком для лапши.

Пример
Входные данные
5 314
0 310 942 628 0
Выходные данные
314 628 1256 942 1570
Примечание

В примере в $$$0$$$-ю минуту за кипятком одновременно захотели пойти $$$1$$$-й и $$$5$$$-й человек, первый вышел сразу и на $$$314$$$-й минуте вернулся от бака. За это время множество желающих выйти за кипятком пополнилось $$$2$$$-м человеком, и следующим пошел $$$2$$$-й человек и т.д. $$$5$$$-й человек в итоге вышел последним.