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

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

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

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

В поезде действует негласное правило: если в какой-то момент возникает ситуация, что за кипятком одновременно могут выйти несколько человек, то выходит только самый левый из них (имеющий место с наименьшим номером), а остальные остаются дожидаться следующего подходящего момента.

Задача состоит в том, чтобы для каждого человека определить, на какой минуте он получит кипяток для своей лапши.

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

Первая строка содержит два целых числа $$$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$$$) — времена, когда соответствующий пассажир вагона захочет выйти за кипятком.

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

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

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

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