Задержки рейсов

문제

Алёна отправляется в долгожданный заслуженный отпуск. Алёна очень боится опоздать на самолёт, поэтому она приехала в аэропорт в момент времени $00$. На табло отправления отображается $nn$ рейсов, рейс номер $ii$ (в нумерации с единицы) должен вылететь в момент времени $t_{i}t\_i$, при этом $t_i>t_{i-1}t\_i\; >\; t\_\{i\; -\; 1\}$ для всех $i\ge 2i\; \backslash geq\; 2$.

К сожалению, погода в городе N очень непредсказуемая, и именно сейчас в районе аэропорта начался сильный снегопад. Для обеспечения безопасности, службы аэропорта должны после отправления каждого рейса снова очищать взлётно-посадочную полосу от снега, поэтому времена отправления двух последовательных рейсов должны отличаться хотя бы на $kk$.

Алёна знает, что рейсы будут отправляться в порядке возрастания своих номеров, при этом каждый рейс будет вылетать настолько рано, насколько это возможно, но не менее чем через $kk$ после вылета предыдущего рейса и не ранее изначально запланированного времени отправления $t_{i}t\_i$.

Поскольку мысли Алёны уже целиком посвящены отпуску, то написать программу, которая определит реальное время отправления каждого из рейсов, предстоит вам. Считайте, что для рейса с номером $11$ нет предыдущего и для него не требуется чистить взлётно-посадочную полосу.

입력

В первой строке входных данных записаны два целых числа $nn$ и $kk$ ($1\le n\le 1000001\; \backslash leq\; n\; \backslash leq\; 100\backslash ,000$, $1\le k\le {10}^{9}1\; \backslash leq\; k\; \backslash leq\; 10^9$) --- количество рейсов, ожидающих отправления, и минимальный необходимый для очистки полосы зазор межу временами отправления двух последовательных самолётов.

Во второй строке записана последовательность целых чисел $t_1,t_2,\dots ,t_{n}t\_1,\; t\_2,\; \backslash ldots,\; t\_n$ () --- запланированные времена отправления рейсов.

출력

Выведите последовательность из $nn$ целых чисел, $ii$-е из которых равняется реальному времени отправления рейса с номером $ii$.

힌트

Рассмотрим первый пример из условия:

1. Первый рейс вылетает в запланированное время.
2. Второй рейс будет задержан из-за необходимости уборки полосы.
3. Запланированной разницы по времени между третьим и вторым рейсом достаточно, чтобы третий рейс вылетел вовремя несмотря на задержку второго рейса и необходимость уборки полосы.
4. Четвёртый рейс вылетает вовремя.
5. Пятый рейс придётся задержать, так как между ним и четвёртым не был запланирован достаточный интервал по времени.
6. Изначально между пятым и шестым рейсом был запланирован интервал времени, достаточный для уборки взлётно-посадочной полосы, но, из-за задержки пятого рейса, шестой рейс так же вылетит с опозданием.