Xếp hàng lấy nước

Một toa tàu có $n$ ghế, đánh số từ $1$ đến $n$ từ trái sang phải, mỗi ghế có đúng một hành khách. Chuyến đi dài, nên đến một lúc nào đó mỗi hành khách sẽ thấy đói và đi lấy nước sôi để pha mì. Hành khách ở ghế $i$ quyết định đi lấy nước tại phút $t_i$.

Bình nước sôi đặt ở bên trái ghế số $1$. Mỗi lần chỉ có một người dùng được bình nước, và mỗi người dùng bình trong đúng $p$ phút. Nếu nhiều người cùng muốn lấy nước, họ sẽ xếp thành một hàng chờ. Thời gian đi từ ghế đến bình nước xem như bằng $0$.

Không ai thích phải đứng xếp hàng. Vì vậy khi hành khách ở ghế $i$ muốn đi lấy nước, trước tiên anh ta nhìn tất cả các ghế từ $1$ đến $i-1$. Nếu có ít nhất một ghế trong số đó đang trống, anh ta cho rằng những người đó đang đứng xếp hàng, nên tạm thời ngồi lại chỗ. Chỉ tại thời điểm đầu tiên anh ta thấy tất cả các ghế có số nhỏ hơn $i$ đều đang có người ngồi, anh ta mới đi ra bình nước (một ghế được coi là trống khi người của ghế đó đang rời chỗ để xếp hàng hoặc đang dùng bình nước).

Có một luật ngầm: nếu tại cùng một thời điểm có nhiều người có thể đi ra bình nước, thì chỉ người ở ghế trái nhất (số ghế nhỏ nhất) mới đi, những người còn lại chờ đến thời điểm tiếp theo.

Hãy tìm, với mỗi hành khách, thời điểm anh ta nhận được nước sôi (thời điểm dùng xong bình nước).

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $p$: số hành khách và thời gian một người dùng bình nước.
• Dòng thứ hai chứa $n$ số nguyên $t_1,t_2,\dots ,t_n$: thời điểm mỗi hành khách muốn đi lấy nước.

Dữ liệu ra

In ra $n$ số nguyên, số thứ $i$ là thời điểm hành khách ở ghế $i$ nhận được nước sôi.

Ràng buộc

• $1\le n\le 100000$
• $1\le p\le {10}^9$
• $0\le t_i\le {10}^9$

Ví dụ