1239_C. Queue in the Train_10493
There are n seats in the train's car and there is exactly one passenger occupying every seat. The seats are numbered from 1 to n from left to right. The trip is long, so each passenger will become hungry at some moment of time and will go to take boiled water for his noodles. The person at seat i (1 ≤ i ≤ n) will decide to go for boiled water at minute t_i.

Tank with a boiled water is located to the left of the 1-st seat. In case too many passengers will go for boiled water simultaneously, they will form a queue, since there can be only one passenger using the tank at each particular moment of time. Each passenger uses the tank for exactly p minutes. We assume that the time it takes passengers to go from their seat to the tank is negligibly small. 

Nobody likes to stand in a queue. So when the passenger occupying the i-th seat wants to go for a boiled water, he will first take a look on all seats from 1 to i - 1. In case at least one of those seats is empty, he assumes that those people are standing in a queue right now, so he would be better seating for the time being. However, at the very first moment he observes that all seats with numbers smaller than i are busy, he will go to the tank.

There is an unspoken rule, that in case at some moment several people can go to the tank, than only the leftmost of them (that is, seating on the seat with smallest number) will go to the tank, while all others will wait for the next moment.

Your goal is to find for each passenger, when he will receive the boiled water for his noodles.

Input

The first line contains integers n and p (1 ≤ n ≤ 100 000, 1 ≤ p ≤ 10^9) — the number of people and the amount of time one person uses the tank.

The second line contains n integers t_1, t_2, ..., t_n (0 ≤ t_i ≤ 10^9) — the moments when the corresponding passenger will go for the boiled water.

Output

Print n integers, where i-th of them is the time moment the passenger on i-th seat will receive his boiled water.

Example

Input


5 314
0 310 942 628 0


Output


314 628 1256 942 1570 

Note

Consider the example.

At the 0-th minute there were two passengers willing to go for a water, passenger 1 and 5, so the first passenger has gone first, and returned at the 314-th minute. At this moment the passenger 2 was already willing to go for the water, so the passenger 2 has gone next, and so on. In the end, 5-th passenger was last to receive the boiled water.
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

from heapq import heappop, heappush, heapify
from collections import deque
class SWAG_Stack():
    def __init__(self, F):
        self.stack1 = deque()
        self.stack2 = deque()
        self.F = F
        self.len = 0

    def push(self, x):
        if self.stack2:
            self.stack2.append((x, self.F(self.stack2[-1][1], x)))
        else:
            self.stack2.append((x, x))
        self.len += 1

    def pop(self):
        if not self.stack1:
            while self.stack2:
                x, _ = self.stack2.pop()
                if self.stack1:
                    self.stack1.appendleft((x, self.F(x, self.stack1[0][1])))
                else:
                    self.stack1.appendleft((x, x))
        x, _ = self.stack1.popleft()
        self.len -= 1
        return x

    def sum_all(self):
        if self.stack1 and self.stack2:
            return self.F(self.stack1[0][1], self.stack2[-1][1])
        elif self.stack1:
            return self.stack1[0][1]
        elif self.stack2:
            return self.stack2[-1][1]
        else:
            return float("inf")

n,p = map(int, input().split())
t = list((j, i) for i,j in enumerate(map(int, input().split())))
heapify(t)

stack = SWAG_Stack(min)

heap = []
cur = 0
ans = [-1]*n
hoge = 0
# 今追加できるやつで最も小さいものを追加
# ここでなにもなかったら？
#   時間を変更する
# 次の時間までに追加できるものを追加
# 清算
while hoge != n:
    if heap and stack.sum_all() > heap[0]:
        j = heappop(heap)
        stack.push(j)

    if stack.len==0 and t:
        cur = max(cur, t[0][0])

    while t and t[0][0] <= cur+p:
        ti, i = heappop(t)
        if ti == cur+p:
            # 後回し
            heappush(heap, i)
        else:
            # いま追加できるか確認
            if stack.sum_all() > i:
                stack.push(i)
            else:
                # 後回し
                heappush(heap, i)

    if stack.len:
        j = stack.pop()
        cur += p
        ans[j] = cur
        hoge += 1
print(*ans)
Below is a problem description that describes the problem. Write code in Python that appropriately solves the problem.

### Description:
There are n seats in the train's car and there is exactly one passenger occupying every seat. The seats are numbered from 1 to n from left to right. The trip is long, so each passenger will become hungry at some moment of time and will go to take boiled water for his noodles. The person at seat i (1 ≤ i ≤ n) will decide to go for boiled water at minute t_i.

Tank with a boiled water is located to the left of the 1-st seat. In case too many passengers will go for boiled water simultaneously, they will form a queue, since there can be only one passenger using the tank at each particular moment of time. Each passenger uses the tank for exactly p minutes. We assume that the time it takes passengers to go from their seat to the tank is negligibly small. 

Nobody likes to stand in a queue. So when the passenger occupying the i-th seat wants to go for a boiled water, he will first take a look on all seats from 1 to i - 1. In case at least one of those seats is empty, he assumes that those people are standing in a queue right now, so he would be better seating for the time being. However, at the very first moment he observes that all seats with numbers smaller than i are busy, he will go to the tank.

There is an unspoken rule, that in case at some moment several people can go to the tank, than only the leftmost of them (that is, seating on the seat with smallest number) will go to the tank, while all others will wait for the next moment.

Your goal is to find for each passenger, when he will receive the boiled water for his noodles.

Input

The first line contains integers n and p (1 ≤ n ≤ 100 000, 1 ≤ p ≤ 10^9) — the number of people and the amount of time one person uses the tank.

The second line contains n integers t_1, t_2, ..., t_n (0 ≤ t_i ≤ 10^9) — the moments when the corresponding passenger will go for the boiled water.

Output

Print n integers, where i-th of them is the time moment the passenger on i-th seat will receive his boiled water.

Example

Input


5 314
0 310 942 628 0


Output


314 628 1256 942 1570 

Note

Consider the example.

At the 0-th minute there were two passengers willing to go for a water, passenger 1 and 5, so the first passenger has gone first, and returned at the 314-th minute. At this moment the passenger 2 was already willing to go for the water, so the passenger 2 has gone next, and so on. In the end, 5-th passenger was last to receive the boiled water.

### Input:
5 314
0 310 942 628 0

### Output:
314 628 1256 942 1570 


### Input:
100 1000000000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

### Output:
1000000001 2000000001 3000000001 4000000001 5000000001 6000000001 7000000001 8000000001 9000000001 10000000001 11000000001 12000000001 13000000001 14000000001 15000000001 16000000001 17000000001 18000000001 19000000001 20000000001 21000000001 22000000001 23000000001 24000000001 25000000001 26000000001 27000000001 28000000001 29000000001 30000000001 31000000001 32000000001 33000000001 34000000001 35000000001 36000000001 37000000001 38000000001 39000000001 40000000001 41000000001 42000000001 43000000001 44000000001 45000000001 46000000001 47000000001 48000000001 49000000001 50000000001 51000000001 52000000001 53000000001 54000000001 55000000001 56000000001 57000000001 58000000001 59000000001 60000000001 61000000001 62000000001 63000000001 64000000001 65000000001 66000000001 67000000001 68000000001 69000000001 70000000001 71000000001 72000000001 73000000001 74000000001 75000000001 76000000001 77000000001 78000000001 79000000001 80000000001 81000000001 82000000001 83000000001 84000000001 85000000001 86000000001 87000000001 88000000001 89000000001 90000000001 91000000001 92000000001 93000000001 94000000001 95000000001 96000000001 97000000001 98000000001 99000000001 100000000001 


### Code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

from heapq import heappop, heappush, heapify
from collections import deque
class SWAG_Stack():
    def __init__(self, F):
        self.stack1 = deque()
        self.stack2 = deque()
        self.F = F
        self.len = 0

    def push(self, x):
        if self.stack2:
            self.stack2.append((x, self.F(self.stack2[-1][1], x)))
        else:
            self.stack2.append((x, x))
        self.len += 1

    def pop(self):
        if not self.stack1:
            while self.stack2:
                x, _ = self.stack2.pop()
                if self.stack1:
                    self.stack1.appendleft((x, self.F(x, self.stack1[0][1])))
                else:
                    self.stack1.appendleft((x, x))
        x, _ = self.stack1.popleft()
        self.len -= 1
        return x

    def sum_all(self):
        if self.stack1 and self.stack2:
            return self.F(self.stack1[0][1], self.stack2[-1][1])
        elif self.stack1:
            return self.stack1[0][1]
        elif self.stack2:
            return self.stack2[-1][1]
        else:
            return float("inf")

n,p = map(int, input().split())
t = list((j, i) for i,j in enumerate(map(int, input().split())))
heapify(t)

stack = SWAG_Stack(min)

heap = []
cur = 0
ans = [-1]*n
hoge = 0
# 今追加できるやつで最も小さいものを追加
# ここでなにもなかったら？
#   時間を変更する
# 次の時間までに追加できるものを追加
# 清算
while hoge != n:
    if heap and stack.sum_all() > heap[0]:
        j = heappop(heap)
        stack.push(j)

    if stack.len==0 and t:
        cur = max(cur, t[0][0])

    while t and t[0][0] <= cur+p:
        ti, i = heappop(t)
        if ti == cur+p:
            # 後回し
            heappush(heap, i)
        else:
            # いま追加できるか確認
            if stack.sum_all() > i:
                stack.push(i)
            else:
                # 後回し
                heappush(heap, i)

    if stack.len:
        j = stack.pop()
        cur += p
        ans[j] = cur
        hoge += 1
print(*ans)