30733번 - Задержки рейсов 다국어

문제

Алёна отправляется в долгожданный заслуженный отпуск. Алёна очень боится опоздать на самолёт, поэтому она приехала в аэропорт в момент времени 0ドル$. На табло отправления отображается $n$ рейсов, рейс номер $i$ (в нумерации с единицы) должен вылететь в момент времени $t_i,ドル при этом $t_i > t_{i - 1}$ для всех $i \geq 2$.

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

Алёна знает, что рейсы будут отправляться в порядке возрастания своих номеров, при этом каждый рейс будет вылетать настолько рано, насколько это возможно, но не менее чем через $k$ после вылета предыдущего рейса и не ранее изначально запланированного времени отправления $t_i$.

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

입력

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

Во второй строке записана последовательность целых чисел $t_1, t_2, \ldots, t_n$ (1ドル \leq t_1 < t_2 < \ldots < t_n \leq 10^{18}$) --- запланированные времена отправления рейсов.

출력

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

제한

노트

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

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