Trên mô hình một con đường một chiều, từ đầu đường cứ cách mỗi mét lại có một lối rẽ phải tạo thành một ngã ba. Ở đầu đường, có 𝑛 xe dàn hàng ngang đánh số từ 1 tới 𝑛 từ trái pha phải, mỗi xe đi trên một làn đường và không có làn đường nào chứa hai xe (xe 𝑛 là xe đi trên làn đường sát lề phải nhất). Các xe cùng xuất phát từ thời điểm 0 và đi với vận tốc không đổi 1 mét/giây.

Xét mỗi xe thứ 𝑖, xe đi trên đường tới ngã ba 𝑎𝑖 thì rẽ phải. Để rẽ phải, trước tiên xe phát tín hiệu và đèn đỏ tại ngã ba đó bật sáng trong đúng Δ giây trên tất cả các làn đường bên phải xe 𝑖. Xe mất đúng Δ giây để rẽ và sau đó xe được coi là không còn trên đường nữa.

Khi một xe gặp đèn đỏ đang bật sáng (do có một xe khác số hiệu nhỏ hơn ở một làn đường bên trái nó đang rẽ phải), xe dừng lại chờ đèn đỏ tắt rồi đi tiếp ngay với vận tốc không đổi 1 mét/giây. Xe không được thay đổi tốc độ hay dừng vì bất cứ lý do nào khác.

Biết rằng không có hai xe nào rẽ phải tại cùng một ngã ba, việc một xe rẽ phải không ảnh hưởng tới các xe số hiệu nhỏ hơn ở các làn đường bên trái xe đang rẽ.

Yêu cầu: Với mỗi xe, xác định thời điểm mà xe đó rời khỏi con đường.

Input:

• Dòng 1 chứa hai số nguyên dương 𝑛, Δ ≤ 10^5 cách nhau ít nhất một dấu cách
• 𝑛 dòng tiếp theo, dòng thứ 𝑖 chứa số nguyên dương 𝑎𝑖 ≤ 10^5

Output:

𝑛 dòng, dòng thứ 𝑖 ghi một số nguyên là thời điểm (tính bằng giây) mà xe 𝑖 rời khỏi con đường.

Sample Input

4 5 
3 
1 
2 
6

Sample Output

8 
6 
12 
21

Sample Input

4 6 
4 
5 
1 
6

Sample Ouput

10 
17 
7 
24