Có $N$ công dân Nga. Mỗi công dân có một số ID quốc gia duy nhất. ID của công dân thứ $i$ là $a[i]$. Tất cả các $a[i]$ đều khác nhau.

Nga có $K$ cái kẹo. Ông ấy quyết định phân phát các cái kẹo này cho công dân theo cách sau cho đến khi hết kẹo:

• Nếu ông ấy có $N$ hoặc nhiều hơn số kẹo, ông ấy sẽ phát 1 cái kẹo cho mỗi công dân.
• Nếu không, để $K'$ là số kẹo ông ấy có tại thời điểm đó, ông ấy sẽ phát 1 cái kẹo cho từng công dân có $K'$ số ID nhỏ nhất.

Khi tất cả kẹo được phát xong, hãy tính số kẹo mà công dân thứ $i$ nhận được.

Input:

Dòng đầu tiên chứa hai số nguyên $N$ và $K$ $(1 \leq N \leq 2 \times 10^5, 1 \leq K \leq 10^{18})$.

Dòng thứ hai chứa $N$ số nguyên khác nhau $a_1, a_2, \ldots, a_N$ $(1 \leq a_i \leq 10^9)$.

Output:
In ra $N$ số, số thứ i biểu thị số kẹo mà công dân thứ i nhận được.

Example:
Sample Input 1:

2 7
1 8

Sample Output 1:

4
3

Note:
Nga sẽ phân phát các mảnh bánh như sau:

• Phát mỗi người một mảnh, Takahashi còn lại 5 mảnh.
• Phát mỗi người một mảnh, Takahashi còn lại 3 mảnh.
• Phát mỗi người một mảnh, Takahashi còn lại 1 mảnh.
• Phát một mảnh cho công dân thứ 1, Takahashi không còn mảnh nào.

Cuối cùng, công dân thứ 1 sẽ nhận được 4 mảnh, và công dân thứ 2 sẽ nhận được 3 mảnh.