Một con Robot được thiết kế để cắt thanh kim loại nằm ngang ban đầu có độ dài m đơn vị độ dài thành các đoạn nhỏ. Robot được lập trình n lần cắt mỗi lần cách mép trái của thanh ban đầu lần lượt là \(a_i\) đơn vị độ dài, sao cho hai lần cắt không bao giờ cùng một vị trí. Người sử dụng Robot muốn biết mỗi lần cắt xong thì độ dài dài nhất của các đoạn con là bao nhiêu. Bạn hãy lập trình nhập vào hai số nguyên dương m, n và dãy số nguyên dương n phần tử khác nhau từng đôi một, chỉ ra n giá trị mỗi giá trị là độ dài đoạn con thu được dài nhất sau từng mỗi lần cắt.

Input

Dòng đầu chứa hai số nguyên dương n, m \((1<=n<=10^5, n<m<=10^6)\)

Dòng thứ hai chứa n số nguyên dương tương ứng với n lần cắt cách mép trái của thanh ban đầu các lần cắt không trùng nhau và \(1<=a_i <m \)

Output

Với sau mỗi nhát cắt chỉ ra độ dài thanh dài nhất hiện thời

Ví dụ 1

Input

5 20
13 8 17 5 9

Output

13 8 8 5 5

Giải thích

Ban đầu thanh dài 20

Sau lần cắt 1 tại vị trí 13: 13 + 7

Sau lần cắt 2 tại vị trí 08: 8 + 5 + 7

Sau lần cắt 3 tại vị trí 17: 8 + 5 + 4 + 3

Sau lần cắt 4 tại vị trí 05: 5 + 3 + 5 + 4 + 3

Sau lần cắt 5 tại vị trí 09: 5 + 3 + 1 + 4 + 4 + 3

Ví dụ 2

Input

10 1000
177 145 608 906 783 735 34 561 464 641

Output

823 823 431 431 431 431 431 384 287 287

Chú ý : Thời gian rất chặt nên dùng scanf và printf thay vì cin và cout